Toward Constant Time Enumeration

• Item type: SIG Technical Reports(1)
• 公開日: 2014-02-24
• タイトル: Toward Constant Time Enumeration
• タイトル / 言語: en
• タイトル: Toward Constant Time Enumeration
• 言語: eng
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: National Institute of Informatics
• 著者所属(英): en
• 著者所属(英): National Institute of Informatics
• 著者名: Takeaki, Uno
• 著者名(英): Takeaki, Uno
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: In this paper, we propose a new amortized analysis for enumeration algorithms. We amortize the computation time of an iteration by charging to all its descendant iterations. We clarify sufficient conditions such that if an enumeration algorithm satisfies the condition, the amortized analysis works. By the amortization, we show that many elimination orderings, matchings in a graph, connected vertex induced subgraphs in a graph, and spanning trees can be enumerated in O(1) time for each solution with simple algorithms and proofs.
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: In this paper, we propose a new amortized analysis for enumeration algorithms. We amortize the computation time of an iteration by charging to all its descendant iterations. We clarify sufficient conditions such that if an enumeration algorithm satisfies the condition, the amortized analysis works. By the amortization, we show that many elimination orderings, matchings in a graph, connected vertex induced subgraphs in a graph, and spanning trees can be enumerated in O(1) time for each solution with simple algorithms and proofs.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2014-AL-147, 号 17, p. 1-8, 発行日 2014-02-24
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会