All geek questions in one place

Algorithm for 2-approximation of the Vertex-Cover task using the "Spanning Tree"

I saw a question about a 2-approximation algorithm for the Vertex-Cap problem (VC, the famous Np-Complete problem), and I don't know the answer. The problem is this: Find a 2-approximation algorithm for the vertex problem using the "Spanning Tree". Well, many greedy approaches are already presented for VC, but the special algorithm using the "Spanning Tree" is complicated. Any ideas?

+4
source share
1 answer

You are just looking for the maximum match in the given graph, and the solution is a set of nodes that create the maximum match.

0
source

Source: https://habr.com/ru/post/1337810/

More articles:


All Articles