n***y
发帖数: 82 | 1 【 以下文字转载自 Programming 讨论区 】
发信人: nofly (nofly), 信区: Programming
标 题: 问个在图中删除边和点的算法问题
发信站: BBS 未名空间站 (Sat Aug 4 00:19:43 2007)
任意的一个图，有点有边。如果删除任何一个点，那么所有与这个点相连的边也都
同时被删除。现在想通过删除尽可能少的点来删除所有的边。比如，如果一个图中
所有的边都和同一个点相连，那么最佳的办法就是删除这个共同点，而不是去删除
所有其他的点。
请问有没有最优的算法？谢谢。 |
c****r
发帖数: 185 | 2 This is the vertex cover problem. NP-hard |
s*******y
发帖数: 558 | 3 我知道polynomial time 2－approximation algorithm来解这个vertex cover problem。
但是如果是按degree从大到小的顺序删除node， 这样得到的cover会比最优大多少呢？
【在 c****r 的大作中提到】
: This is the vertex cover problem. NP-hard
|
n***y
发帖数: 82 | 4 Thanks.
【在 c****r 的大作中提到】
: This is the vertex cover problem. NP-hard
|
