Generating all maximal induced subgraphs for hereditary and connected-hereditary graph properties
type: Item
instance of: scholarly article
title: Generating all maximal induced subgraphs for hereditary and connected-hereditary graph properties
zbMATH Open document ID: 1152.68040
author: Benny Kimelfeld
author: Yehoshua Sagiv
author: Sara Cohen
published in: Journal of Computer and System Sciences
publication date: 2008-11-19T00:00:00Z
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C40
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68Q15
zbMATH DE Number: 5369044
zbMATH Keywords: enumeration
zbMATH Keywords: graph properties
zbMATH Keywords: hereditary properties
zbMATH Keywords: maximal subgraphs
zbMATH Keywords: complexity classes
MaRDI profile type: Publication
full work available at URL: j.jcss.2008.04.003
OpenAlex ID: W1978544932
cites work: On the complexity of the Maximum Subgraph Problem
cites work: Node-and edge-deletion NP-complete problems
cites work: The node-deletion problem for hereditary properties is NP-complete
cites work: A new approach for approximating node deletion problems
cites work: A unified approximation algorithm for node-deletion problems
cites work: The approximation of maximum subgraph problems
cites work: Approximating Clique and Biclique Problems
cites work: Additive approximation for edge-deletion problems
cites work: Q4228508
cites work: The speed of hereditary properties of graphs
cites work: Graph Sandwich Problems
cites work: Q4448769
cites work: On generating all maximal independent sets
cites work: A New Algorithm for Generating All the Maximal Independent Sets
cites work: The Enumeration of Maximal Cliques of Large Graphs
cites work: Algorithm Theory - SWAT 2004
cites work: Bounds on Backtrack Algorithms for Listing Cycles, Paths, and Spanning Trees
cites work: Algorithms for Enumerating All Spanning Trees of Undirected and Weighted Graphs
cites work: Finding All Spanning Trees of Directed and Undirected Graphs
cites work: Graph-Theoretic Concepts in Computer Science
cites work: Enumeration of acyclic walks in a graph
cites work: Reverse search for enumeration
cites work: Algorithms and Computation
cites work: Q4414542
cites work: Database Theory - ICDT 2005
cites work: Q4198056
cites work: The Complexity of Enumeration and Reliability Problems
cites work: The complexity of computing the permanent
cites work: Database Programming Languages
DOI: 10.1016/J.JCSS.2008.04.003
description: scientific article; zbMATH DE number 5369044