- Type Parameters:
V- the graph vertex type
E- the graph edge type
- All Implemented Interfaces:
public class BarYehudaEvenTwoApproxVCImpl<V,E> extends java.lang.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!
- Joris Kinable
Constructors Constructor Description
BarYehudaEvenTwoApproxVCImpl(Graph<V,E> graph)Constructs a new BarYehudaEvenTwoApproxVCImpl instance where all vertices have uniform weights.
BarYehudaEvenTwoApproxVCImpl(Graph<V,E> graph, java.util.Map<V,java.lang.Double> vertexWeightMap)Constructs a new BarYehudaEvenTwoApproxVCImpl instance
All Methods Instance Methods Concrete Methods Modifier and Type Method Description
getVertexCover()Computes a vertex cover.
BarYehudaEvenTwoApproxVCImplConstructs a new BarYehudaEvenTwoApproxVCImpl instance where all vertices have uniform weights.
graph- input graph