Graph Decomposition
Lists
Only you see this
Abstract
For some graph problems, the fact of restricting the input to planar graphs simplifies the computational complexity of the problem. However, there are some NP-complete problems that remain NP-complete even when restricted to planar graphs, for instance the Maximum Independent Set problem (see [GJ79]). We have already mentioned in the introduction that to find a constant approximation to the problem of the Maximum Independent Set for a general graph with n vertices is as difficult as to find an approximation to the problem of finding a Maximum Clique, which means that unless P=NP, the Maximum Independent Set problem cannot be approximated within n1−ε [Has96].
BibTeX
@inproceedings{daz1997graph,
author = {Josep Dı́az and Marı́a Serna and Paul G. Spirakis and Jacobo Torán},
title = {{Graph Decomposition}},
booktitle = {Cambridge},
year = {1997},
doi = {10.1017/cbo9780511666407.007},
}Loading related content...