开发者

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

开发者 https://www.devze.com 2023-02-07 22:40 出处:网络
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 algorit

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

精彩评论

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