A constant amortized time enumeration algorithm for independent sets in graphs with bounded clique number
Publication:2034408
DOI10.1016/J.TCS.2021.05.008OpenAlexW2960749100MaRDI QIDQ2034408FDOQ2034408
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
Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Enumeration in graph theory (05C30)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Smallest-last ordering and clustering and graph coloring algorithms
- A New Algorithm for Generating All the Maximal Independent Sets
- k-Degenerate Graphs
- On maximal independent sets of vertices in claw-free graphs
- Reverse search for enumeration
- Sparsity. Graphs, structures, and algorithms
- On generating all maximal independent sets
- 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
- The worst-case time complexity for generating all maximal cliques and computational experiments
- Algorithm Theory - SWAT 2004
- Small Maximal Independent Sets and Faster Exact Graph Coloring
- Counting the number of independent sets in chordal graphs
- A new decomposition technique for maximal clique enumeration for sparse graphs
- An Optimal Algorithm for Scanning All Spanning Trees of Undirected Graphs
- Fast algorithms for generating all maximal independent sets of interval, circular-arc and chordal graphs
- Generating all maximal induced subgraphs for hereditary and connected-hereditary graph properties
- Optimal Listing of Cycles and st-Paths in Undirected Graphs
- Efficient enumeration of bipartite subgraphs in graphs
- Efficient Enumeration of Induced Subtrees in a K-Degenerate Graph
- Constant Time Enumeration by Amortization
- Listing Maximal Subgraphs Satisfying Strongly Accessible Properties
- Listing Maximal Independent Sets with Minimal Space and Bounded Delay
- New polynomial delay bounds for maximal subgraph enumeration by proximity search
- Amortized $\tilde{O}(|V|)$ -Delay Algorithm for Listing Chordless Cycles in Undirected Graphs
- Enumerating Minimal Dominating Sets in Triangle-Free Graphs
Cited In (1)
This page was built for publication: A constant amortized time enumeration algorithm for independent sets in graphs with bounded clique number
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2034408)
