http://swrc.ontoware.org/ontology#TechnicalReport
Constant Amortized Time Enumeration of Eulerian trails
en
National Institute of Informatics
Presently with Toyohashi University of Technology
Kazuhiro Kurita
Kunihiro Wasa
In this paper, we consider enumeration problems for edge-distinct and vertex-distinct Eulerian trails. Here, two Eulerian trails are edge-distinct if the edge sequences are not identical, and they are vertex-distinct if the vertex sequences are not identical. As the main result, we propose optimal enumeration algorithms for both problems, that is, these algorithm runs in O(N) total time, where N is the number of solutions. Our algorithms are based on the reverse search technique introduced by [Avis and Fukuda, DAM 1996], and the push out amortization technique introduced by [Uno, WADS 2015].
In this paper, we consider enumeration problems for edge-distinct and vertex-distinct Eulerian trails. Here, two Eulerian trails are edge-distinct if the edge sequences are not identical, and they are vertex-distinct if the vertex sequences are not identical. As the main result, we propose optimal enumeration algorithms for both problems, that is, these algorithm runs in O(N) total time, where N is the number of solutions. Our algorithms are based on the reverse search technique introduced by [Avis and Fukuda, DAM 1996], and the push out amortization technique introduced by [Uno, WADS 2015].
AN1009593X
研究報告アルゴリズム（AL）
2021-AL-183
17
1-6
2021-04-30
2188-8566