Solving NP-hard problems in 'almost trees': vertex cover (Q1062757)

In the paper a new algorithm which finds a minimum vertex cover in a graph G, is proposed. Its complexity depends linearly on the number of vertices of G and exponentially on the maximum a over all biconnected components of the graph, where a is defined as the minimum number of edges that must be added to a tree to produce G. A parallel implementation of the algorithm is also given.