我在教科书中找到了这段伪代码，但我没有正确理解它，而且解释得很差。
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 Problem presentation 的第 8 页找到这个特定的算法。由 Gajanand Sharma 提供。
它似乎被称为Approx-Vertex-Cover，也称为顶点覆盖近似算法。
在后续页面中，有一个有关该算法及其工作原理的示例。
也在 Approximation Algorithms: Vertex Cover document在第 2 页，您可以找到另一个很好的解释:
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
关于graph-theory - 这个解决NP-Hard Vertex Cover的贪心算法叫什么名字，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/36807324/