Constant Time Enumeration by Amortization

DOI10.1007/978-3-319-21840-3_49zbMath1451.68361arXiv1407.3857OpenAlexW2404007012MaRDI QIDQ3449856

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

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

Related Items (7)

Enumeration of support-closed subsets in confluent systems ⋮ Constant amortized time enumeration of Eulerian trails ⋮ Polynomial-delay and polynomial-space enumeration of large maximal matchings ⋮ Linear amortized time enumeration algorithms for compatible Euler trails in edge-colored graphs ⋮ 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 ⋮ Enumerating connected induced subgraphs: improved delay and experimental comparison

Cites Work

• Unnamed Item
• Enumeration of the perfect sequences of a chordal graph
• Generating and characterizing the perfect elimination orderings of a chordal graph
• Reverse search for enumeration
• Output-Sensitive Listing of Bounded-Size Trees in Undirected Graphs
• Algorithmic Aspects of Vertex Elimination on Graphs
• An Optimal Algorithm for Scanning All Spanning Trees of Undirected Graphs
• Algorithms for Enumerating All Spanning Trees of Undirected and Weighted Graphs
• Finding the k smallest spanning trees

This page was built for publication: Constant Time Enumeration by Amortization