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.
精彩评论