2026-04-18T13:50:50Z https://ipsj.ixsq.nii.ac.jp/oai

oai:ipsj.ixsq.nii.ac.jp:00098738 2025-01-21T12:20:36Z 1164:2592:7425:7467

Toward Constant Time Enumeration Toward Constant Time Enumeration Takeaki, Uno Takeaki, Uno 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. 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. 情報処理学会 2014-02-24 eng technical report https://ipsj.ixsq.nii.ac.jp/records/98738 AN1009593X 研究報告アルゴリズム（AL） 2014-AL-147 17 1 8 https://ipsj.ixsq.nii.ac.jp/record/98738/files/IPSJ-AL14147017.pdf application/pdf 677.2 kB 2016-02-24