C. Lund, und M. Yannakakis. Automata, Languages and Programming, Seite 40--51. Berlin, Heidelberg, Springer Berlin Heidelberg, (1993)
Zusammenfassung
We consider the following class of problems: given a graph, find the maximum number of nodes inducing a subgraph that satisfies a desired property $\pi$, such as planar, acyclic, bipartite, etc. We show that this problem is hard to approximate for any property $\pi$ on directed or undirected graphs that is nontrivial and hereditary on induced subgraphs.
%0 Conference Paper
%1 10.1007/3-540-56939-1_60
%A Lund, Carsten
%A Yannakakis, Mihalis
%B Automata, Languages and Programming
%C Berlin, Heidelberg
%D 1993
%E Lingas, Andrzej
%E Karlsson, Rolf
%E Carlsson, Svante
%I Springer Berlin Heidelberg
%K approximation node_deletion_problem np_complete
%P 40--51
%T The approximation of maximum subgraph problems
%X We consider the following class of problems: given a graph, find the maximum number of nodes inducing a subgraph that satisfies a desired property $\pi$, such as planar, acyclic, bipartite, etc. We show that this problem is hard to approximate for any property $\pi$ on directed or undirected graphs that is nontrivial and hereditary on induced subgraphs.
%@ 978-3-540-47826-3
@inproceedings{10.1007/3-540-56939-1_60,
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 $\pi$, such as planar, acyclic, bipartite, etc. We show that this problem is hard to approximate for any property $\pi$ on directed or undirected graphs that is nontrivial and hereditary on induced subgraphs.},
added-at = {2019-06-05T13:33:33.000+0200},
address = {Berlin, Heidelberg},
author = {Lund, Carsten and Yannakakis, Mihalis},
biburl = {https://www.bibsonomy.org/bibtex/2ec2153051ac1dcf1e37678e2a4182864/duerrschnabel},
booktitle = {Automata, Languages and Programming},
editor = {Lingas, Andrzej and Karlsson, Rolf and Carlsson, Svante},
interhash = {182f4ca38b3aadd66f5b5000a10491c1},
intrahash = {ec2153051ac1dcf1e37678e2a4182864},
isbn = {978-3-540-47826-3},
keywords = {approximation node_deletion_problem np_complete},
pages = {40--51},
publisher = {Springer Berlin Heidelberg},
timestamp = {2019-06-05T13:33:33.000+0200},
title = {The approximation of maximum subgraph problems},
year = 1993
}