Listing Maximal Independent Sets with Minimal Space and Bounded Delay

DOI10.1007/978-3-319-67428-5_13zbMath1454.68097OpenAlexW2752348400MaRDI QIDQ5150928

Takeaki Uno, Alessio Conte, Luca Versari, Roberto Grossi, Andrea Marino

Publication date: 16 February 2021

Published in: String Processing and Information Retrieval (Search for Journal in Brave)

Full work available at URL: https://hal.inria.fr/hal-01609012/file/conte_etal_2017.pdf

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items

Unnamed Item, Listing Maximal Subgraphs Satisfying Strongly Accessible Properties, Efficiently enumerating minimal triangulations, Maximal strongly connected cliques in directed graphs: algorithms and bounds, Sublinear-space and bounded-delay algorithms for maximal clique enumeration in graphs, Unnamed Item, A constant amortized time enumeration algorithm for independent sets in graphs with bounded clique number

Uses Software

• Algorithm 457

Cites Work

• Unnamed Item
• 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 depth first search algorithm to generate the family of maximal independent sets of a graph lexicographically
• An improved upper bound on maximal clique listing via rectangular fast matrix multiplication
• Reverse search for enumeration
• Fast maximal cliques enumeration in sparse graphs
• Fast algorithms for generating all maximal independent sets of interval, circular-arc and chordal graphs
• Arboricity and Subgraph Listing Algorithms
• A New Algorithm for Generating All the Maximal Independent Sets
• Generate all maximal independent sets in permutation graphs
• Listing All Maximal Cliques in Large Sparse Real-World Graphs
• Algorithm Theory - SWAT 2004
• Algorithm 457: finding all cliques of an undirected graph
• Graph-Theoretic Concepts in Computer Science
• Finding a maximal weighted independent set in wireless networks