A constant amortized time enumeration algorithm for independent sets in graphs with bounded clique number
From MaRDI portal
Publication:2034408
DOI10.1016/j.tcs.2021.05.008OpenAlexW2960749100MaRDI QIDQ2034408
Kazuhiro Kurita, Takeaki Uno, Hiroki Arimura, Kunihiro Wasa
Publication date: 22 June 2021
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1906.09680
Enumeration in graph theory (05C30) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Sparsity. Graphs, structures, and algorithms
- The worst-case time complexity for generating all maximal cliques and computational experiments
- Counting the number of independent sets in chordal graphs
- Generating all maximal induced subgraphs for hereditary and connected-hereditary graph properties
- On generating all maximal independent sets
- On maximal independent sets of vertices in claw-free graphs
- A new decomposition technique for maximal clique enumeration for sparse graphs
- Efficient enumeration of bipartite subgraphs in graphs
- Reverse search for enumeration
- Amortized $\tilde{O}(|V|)$ -Delay Algorithm for Listing Chordless Cycles in Undirected Graphs
- Efficient Enumeration of Induced Subtrees in a K-Degenerate Graph
- Fast algorithms for generating all maximal independent sets of interval, circular-arc and chordal graphs
- Constant Time Enumeration by Amortization
- Smallest-last ordering and clustering and graph coloring algorithms
- Generation of maximum independent sets of a bipartite graph and maximum cliques of a circular-arc graph
- Bounds on Backtrack Algorithms for Listing Cycles, Paths, and Spanning Trees
- A New Algorithm for Generating All the Maximal Independent Sets
- An Optimal Algorithm for Scanning All Spanning Trees of Undirected Graphs
- Small Maximal Independent Sets and Faster Exact Graph Coloring
- Listing Maximal Subgraphs Satisfying Strongly Accessible Properties
- Enumerating Minimal Dominating Sets in Triangle-Free Graphs
- Listing Maximal Independent Sets with Minimal Space and Bounded Delay
- New polynomial delay bounds for maximal subgraph enumeration by proximity search
- Algorithm Theory - SWAT 2004
- k-Degenerate Graphs
- Optimal Listing of Cycles and st-Paths in Undirected Graphs
