开发者

A 2-approximation algorithm for Vertex-Cover problem using "Spanning Tree"

I have seen a question on 2-approximation algorithm for Vertex-Cover problem(VC, known Np-Complete problem), and i don't know the answer. The problem is the following : Find a 2-approximation algorithm for Vertex Cover problem using "Spanning Tree". Well, many greedy approaches are already p开发者_C百科resented for VC, but special algorithm using "Spanning Tree" is challenging. Any idea?


You just search for max matching in the given graph and the solution is the set of nodes that create a max matching.

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜