这个解决 NP-Hard Vertex Cover 的贪心算法叫什么名字
What is the name of this greedy algorithm to solve NP-Hard Vertex Cover
我在教科书上找到了这个伪代码，但我没有正确理解它，而且解释得不好。
Algorithm 8: Greedy Vertex Cover Algorithm Example(G=(V,E))
1) C := ;.
2) while (E 6= ;)
• Select a node v of maximal degree in G.
• C := C [{v}.
• Remove all edges e from E that are covered by v,
i.e. for which e\v 6= ; holds.
3) Return C.
该算法是解决Vertex Cover问题的贪心算法。有人认识它并知道它的名字吗？我想了解更多。
我想您可以在 Gajanand Sharma 提供的 Vertex Cover Problem presentation 的第 8 页找到这个特定的算法。
好像叫Approx-Vertex-Cover也叫Vertex Cover Approximation Algorithm.
在后续页面中有一个关于该算法及其工作原理的示例。
在第 2 页的 Approximation Algorithms: Vertex Cover document 中您还可以找到另一个很好的解释：
Algorithm 1: Approx-Vertex-Cover(G)
1 C←∅
2 while E 6= ∅
pick any {u, v} ∈ E
C ← C ∪ {u, v}
delete all edges incident to either u or v
return C
我在教科书上找到了这个伪代码，但我没有正确理解它，而且解释得不好。
Algorithm 8: Greedy Vertex Cover Algorithm Example(G=(V,E))
1) C := ;.
2) while (E 6= ;)
• Select a node v of maximal degree in G.
• C := C [{v}.
• Remove all edges e from E that are covered by v,
i.e. for which e\v 6= ; holds.
3) Return C.
该算法是解决Vertex Cover问题的贪心算法。有人认识它并知道它的名字吗？我想了解更多。
我想您可以在 Gajanand Sharma 提供的 Vertex Cover Problem presentation 的第 8 页找到这个特定的算法。
好像叫Approx-Vertex-Cover也叫Vertex Cover Approximation Algorithm.
在后续页面中有一个关于该算法及其工作原理的示例。
在第 2 页的 Approximation Algorithms: Vertex Cover document 中您还可以找到另一个很好的解释：
Algorithm 1: Approx-Vertex-Cover(G)
1
C←∅2
while E 6= ∅pick any {u, v} ∈ E C ← C ∪ {u, v} delete all edges incident to either u or v
return C