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

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

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

• scientific article; zbMATH DE number 1405693 (Why is no real title available?)
• 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
• Output-sensitive listing of bounded-size trees in undirected graphs
• Reverse search for enumeration

Cited in

(10)

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

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)