Constant Amortized Time Enumeration of Eulerian trails

• Item type: SIG Technical Reports(1)
• 公開日: 2021-04-30
• タイトル: Constant Amortized Time Enumeration of Eulerian trails
• タイトル / 言語: en
• タイトル: Constant Amortized Time Enumeration of Eulerian trails
• 言語: eng
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: National Institute of Informatics
• 著者所属: Presently with Toyohashi University of Technology
• 著者所属(英): en
• 著者所属(英): National Institute of Informatics
• 著者所属(英): en
• 著者所属(英): Presently with Toyohashi University of Technology
• 著者名: Kazuhiro, Kurita; Kunihiro, Wasa
• 著者名(英): Kazuhiro, Kurita; Kunihiro, Wasa
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 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].
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: 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].
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2021-AL-183, 号 17, p. 1-6, 発行日 2021-04-30
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8566
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会