Back to Search Start Over

The approximation of maximum subgraph problems

Authors :
Mihalis Yannakakis
Carsten Lund
Source :
Automata, Languages and Programming ISBN: 9783540569398, ICALP
Publication Year :
1993
Publisher :
Springer Berlin Heidelberg, 1993.

Abstract

We consider the following class of problems: given a graph, find the maximum number of nodes inducing a subgraph that satisfies a desired property π, such as planar, acyclic, bipartite, etc. We show that this problem is hard to approximate for any property π on directed or undirected graphs that is nontrivial and hereditary on induced subgraphs.

Subjects

Subjects :
Discrete mathematics
Mathematics::Combinatorics
Subgraph isomorphism problem
Maximum common subgraph isomorphism problem
Planar graph
Combinatorics
symbols.namesake
Computer Science::Discrete Mathematics
TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY
symbols
Bipartite graph
Graph (abstract data type)
Induced subgraph isomorphism problem
Hereditary property
Computer Science::Data Structures and Algorithms
Graph property
MathematicsofComputing_DISCRETEMATHEMATICS
Mathematics

Details

ISBN :
978-3-540-56939-8
ISBNs :
9783540569398
Database :
OpenAIRE
Journal :
Automata, Languages and Programming ISBN: 9783540569398, ICALP
Accession number :
edsair.doi...........c72ae4e13d1b7760f84a294043143aea
Full Text :
https://doi.org/10.1007/3-540-56939-1_60
Full Text Access
View/download PDF

Tools

Authors Abstract Subjects Details