2026-04-11T12:23:44Z https://ipsj.ixsq.nii.ac.jp/oai

oai:ipsj.ixsq.nii.ac.jp:00210993 2025-01-19T17:56:59Z 1164:2592:10486:10582

Constant Amortized Time Enumeration of Eulerian trails Constant Amortized Time Enumeration of Eulerian trails Kazuhiro, Kurita Kunihiro, Wasa 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]. technical report 情報処理学会 2021-04-30 application/pdf 研究報告アルゴリズム（AL） 17 2021-AL-183 1 6 2188-8566 AN1009593X https://ipsj.ixsq.nii.ac.jp/record/210993/files/IPSJ-AL21183017.pdf eng