Toward Constant Time Enumeration

スポンサーリンク

概要

• 論文の詳細を見る

• 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

著者

• Takeaki Uno

  National Institute Of Informatics

関連論文

• The Complexity of Free Flood Filling Games
• Hardness Results and an Exact Exponential Algorithm for the Spanning Tree Congestion Problem
• On the number of reduced trees, cographs, and series-parallel graphs by compression
• Algorithm to Generate All Connected Simple Graphs of Given Order
• An Algorithm for Finding Frequently Appearing Long String Patterns from Large Scale Databases
• Toward Constant Time Enumeration

スポンサーリンク