Constant time enumeration by amortization

DOI10.1007/978-3-319-21840-3_49MaRDI QIDQ3449856zbMATH OpenOpenAlexFDO

Authors Takeaki Uno

Publication date 30 October 2015

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1407.3857

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40)

Abstract: Enumeration algorithms have been one of recent hot topics in theoretical computer science. Different from other problems, enumeration has many interesting aspects, such as the computation time can be shorter than the total output size, by sophisticated ordering of output solutions. One more example is that the recursion of the enumeration algorithm is often structured well, thus we can have good amortized analysis, and interesting algorithms for reducing the amortized complexity. However, there is a lack of deep studies from these points of views; there are only few results on the fundamentals of enumeration, such as a basic design of an algorithm that is applicable to many problems. In this paper, we address new approaches on the complexity analysis, and propose a new way of amortized analysis Push-Out Amortization for enumeration algorithms, where the computation time of an iteration is amortized by using all its descendant iterations. We clarify sufficient conditions on the enumeration algorithm so that 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 by simple algorithms with simple proofs.

Recommendations

• Publication:4938674
• A constant amortized time enumeration algorithm for independent sets in graphs with bounded clique number
• Enumeration complexity
• Incremental delay enumeration: space and time
• Constant time enumeration of bounded-size subtrees in trees and its application

Cites work

• Algorithmic Aspects of Vertex Elimination on Graphs
• Algorithms for Enumerating All Spanning Trees of Undirected and Weighted Graphs
• An Optimal Algorithm for Scanning All Spanning Trees of Undirected Graphs
• Enumeration of the perfect sequences of a chordal graph
• Finding the k smallest spanning trees
• Generating and characterizing the perfect elimination orderings of a chordal graph
• scientific article; zbMATH DE number 1405693 (Why is no real title available?)
• Output-sensitive listing of bounded-size trees in undirected graphs
• Reverse search for enumeration

Cited in

(11)

• Enumerating models of DNF faster: breaking the dependency on the formula size
• A constant amortized time enumeration algorithm for independent sets in graphs with bounded clique number
• Enumeration of support-closed subsets in confluent systems
• Constant amortized time enumeration of Eulerian trails
• Linear amortized time enumeration algorithms for compatible Euler trails in edge-colored graphs
• Simple constant amortized time generation of fixed length numeric partitions
• Enumerating connected induced subgraphs: improved delay and experimental comparison
• Polynomial-delay and polynomial-space enumeration of large maximal matchings
• Cut vertex and unicyclic graphs with the maximum number of connected induced subgraphs
• Enumerating graphlets with amortized time complexity independent of graph size
• From amortized to worst case delay in enumeration algorithms

This page was built for publication: Constant time enumeration by amortization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3449856)