2022-01-20T15:02:23Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmh
oai:ipsj.ixsq.nii.ac.jp:002109932021-04-29T15:00:00Z01164:02592:10486:10582
Constant Amortized Time Enumeration of Eulerian trailsConstant Amortized Time Enumeration of Eulerian trailsenghttp://id.nii.ac.jp/1001/00210887/Technical Reporthttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=210993&item_no=1&attribute_id=1&file_no=1Copyright (c) 2021 by the Information Processing Society of JapanNational Institute of InformaticsPresently with Toyohashi University of TechnologyKazuhiro, KuritaKunihiro, WasaIn 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-18317162021-04-302188-85662021-04-27