Generating all maximal induced subgraphs for hereditary and connected-hereditary graph properties

DOI10.1016/j.jcss.2008.04.003zbMath1152.68040OpenAlexW1978544932MaRDI QIDQ955347

Benny Kimelfeld, Yehoshua Sagiv, Sara A. Cohen

Publication date: 19 November 2008

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2008.04.003

zbMATH Keywords

enumerationgraph propertieshereditary propertiescomplexity classesmaximal subgraphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Connectivity (05C40)

Related Items (15)

Enumeration of support-closed subsets in confluent systems ⋮ Proximity Search for Maximal Subgraph Enumeration ⋮ Polynomial-delay and polynomial-space enumeration of large maximal matchings ⋮ Polynomial-delay enumeration algorithms in set systems ⋮ Efficient enumeration of maximal split subgraphs and induced sub-cographs and related classes ⋮ Listing Maximal Subgraphs Satisfying Strongly Accessible Properties ⋮ Listing Maximal Independent Sets with Minimal Space and Bounded Delay ⋮ Efficiently enumerating minimal triangulations ⋮ Maximal strongly connected cliques in directed graphs: algorithms and bounds ⋮ Efficient enumeration of maximal induced bicliques ⋮ 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 ⋮ Unnamed Item ⋮ Transducing Markov sequences

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of computing the permanent
• Enumeration of acyclic walks in a graph
• A new approach for approximating node deletion problems
• On generating all maximal independent sets
• The node-deletion problem for hereditary properties is NP-complete
• A unified approximation algorithm for node-deletion problems
• The speed of hereditary properties of graphs
• Reverse search for enumeration
• Additive approximation for edge-deletion problems
• The Complexity of Enumeration and Reliability Problems
• Bounds on Backtrack Algorithms for Listing Cycles, Paths, and Spanning Trees
• A New Algorithm for Generating All the Maximal Independent Sets
• Finding All Spanning Trees of Directed and Undirected Graphs
• Approximating Clique and Biclique Problems
• The approximation of maximum subgraph problems
• Algorithms for Enumerating All Spanning Trees of Undirected and Weighted Graphs
• Graph Sandwich Problems
• Algorithm Theory - SWAT 2004
• Database Theory - ICDT 2005
• Node-and edge-deletion NP-complete problems
• On the complexity of the Maximum Subgraph Problem
• Database Programming Languages
• The Enumeration of Maximal Cliques of Large Graphs
• Graph-Theoretic Concepts in Computer Science
• Algorithms and Computation

This page was built for publication: Generating all maximal induced subgraphs for hereditary and connected-hereditary graph properties