w******T
发帖数: 71 | 1 Given a graph cubic planar graph,
to get maximum independent set of it is NP-hard.
Does any body know this problem admits PTAS or not?
If not, what is the lower bound for it.
Thanks a lot. | y***u
发帖数: 101 | 2 http://www.nada.kth.se/~viggo/wwwcompendium/node34.html
【在 w******T 的大作中提到】
: Given a graph cubic planar graph,
: to get maximum independent set of it is NP-hard.
: Does any body know this problem admits PTAS or not?
: If not, what is the lower bound for it.
: Thanks a lot.
|
|
