org.jgrapht.alg.vertexcover

## Class BarYehudaEvenTwoApproxVCImpl<V,E>

• java.lang.Object
• org.jgrapht.alg.vertexcover.BarYehudaEvenTwoApproxVCImpl<V,E>
• Type Parameters:
V - the graph vertex type
E - the graph edge type
All Implemented Interfaces:
VertexCoverAlgorithm<V>

public class BarYehudaEvenTwoApproxVCImpl<V,E>
extends Object
implements VertexCoverAlgorithm<V>
Implementation of the 2-opt algorithm for a minimum weighted vertex cover by R. Bar-Yehuda and S. Even. A linear time approximation algorithm for the weighted vertex cover problem. J. of Algorithms 2:198-203, 1981. The solution is guaranteed to be within $2$ times the optimum solution. An easier-to-read version of this algorithm can be found here: https://www.cs.umd.edu/class/spring2011/cmsc651/vc.pdf Note: this class supports pseudo-graphs Runtime: $O(|E|)$ This is a fast algorithm, guaranteed to give a $2$-approximation. A solution of higher quality (same approximation ratio) at the expensive of a higher runtime can be obtained using BarYehudaEvenTwoApproxVCImpl. TODO: Remove the UndirectedSubgraph dependency! Querying vertex degrees on these graphs is actually slow! This does affect the runtime complexity. Better would be to just work on a clone of the original graph!
Author:
Joris Kinable
• ### Constructor Detail

• #### BarYehudaEvenTwoApproxVCImpl

public BarYehudaEvenTwoApproxVCImpl(Graph<V,E> graph)
Constructs a new BarYehudaEvenTwoApproxVCImpl instance where all vertices have uniform weights.
Parameters:
graph - input graph
• #### BarYehudaEvenTwoApproxVCImpl

public BarYehudaEvenTwoApproxVCImpl(Graph<V,E> graph,
Map<V,Double> vertexWeightMap)
Constructs a new BarYehudaEvenTwoApproxVCImpl instance
Parameters:
graph - input graph
vertexWeightMap - mapping of vertex weights