2026-04-10T21:15:52Z 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]. 情報処理学会 2021-04-30 eng technical report https://ipsj.ixsq.nii.ac.jp/records/210993 2188-8566 AN1009593X 研究報告アルゴリズム（AL） 2021-AL-183 17 1 6 https://ipsj.ixsq.nii.ac.jp/record/210993/files/IPSJ-AL21183017.pdf application/pdf 705.5 kB 2023-04-30