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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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.
|
|