n***y
发帖数: 82 | 1 任意的一个图，有点有边。如果删除任何一个点，那么所有与这个点相连的边也都
同时被删除。现在想通过删除尽可能少的点来删除所有的边。比如，如果一个图中
所有的边都和同一个点相连，那么最佳的办法就是删除这个共同点，而不是去删除
所有其他的点。
请问有没有最优的算法？谢谢。 |
N********n
发帖数: 8363 | 2 Sounds like a register allocation or graph coloring problem in compiler
design. It's one hard problem. There are a few heuristics for it.
【在 n***y 的大作中提到】
: 任意的一个图，有点有边。如果删除任何一个点，那么所有与这个点相连的边也都
: 同时被删除。现在想通过删除尽可能少的点来删除所有的边。比如，如果一个图中
: 所有的边都和同一个点相连，那么最佳的办法就是删除这个共同点，而不是去删除
: 所有其他的点。
: 请问有没有最优的算法？谢谢。
|
c*****t
发帖数: 1879 | 3 I think that this is NPC since if it polynomial, we can use it to find
cliques.
【在 n***y 的大作中提到】
: 任意的一个图，有点有边。如果删除任何一个点，那么所有与这个点相连的边也都
: 同时被删除。现在想通过删除尽可能少的点来删除所有的边。比如，如果一个图中
: 所有的边都和同一个点相连，那么最佳的办法就是删除这个共同点，而不是去删除
: 所有其他的点。
: 请问有没有最优的算法？谢谢。
|
s*******y
发帖数: 558 | 4 恩 这是 vertex cover problem， 去找approximation的算法吧
【在 c*****t 的大作中提到】
: I think that this is NPC since if it polynomial, we can use it to find
: cliques.
|
n***y
发帖数: 82 | 5 You are right. Thanks.
【在 s*******y 的大作中提到】
: 恩 这是 vertex cover problem， 去找approximation的算法吧
|
