Back to Search
Start Over
Constant amortized time enumeration of Eulerian trails.
- Source :
-
Theoretical Computer Science . Jun2022, Vol. 923, p1-12. 12p. - Publication Year :
- 2022
-
Abstract
- • Eulerian trails are classical and important objects in theoretical computer science field. • Enumeration of Eulerian trails is known to be #P-complete. • Although the existence of an algorithm with linear time per output is known, the existence of a faster algorithm is open. • This paper shows optimal algorithms for Eulerian trails which run in constant time per solution on average. In this paper, we consider enumeration problems for edge-distinct and vertex-distinct Eulerian trails. Two Eulerian trails are said to be edge-distinct if the edge sequences are not identical, and they are said to be vertex-distinct if the vertex sequences are not identical. To solve these problems, we propose optimal enumeration algorithms that run in O (N + m) total time, where N is the number of solutions and m is the number of edges in an input connected graph. The proposed 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]. [ABSTRACT FROM AUTHOR]
- Subjects :
- *EULERIAN graphs
*COMPUTER science
*PROBLEM solving
Subjects
Details
- Language :
- English
- ISSN :
- 03043975
- Volume :
- 923
- Database :
- Academic Search Index
- Journal :
- Theoretical Computer Science
- Publication Type :
- Academic Journal
- Accession number :
- 157328795
- Full Text :
- https://doi.org/10.1016/j.tcs.2022.04.048