Class BarYehudaEvenTwoApproxVCImpl<V,​E>

  • Type Parameters:
    V - the graph vertex type
    E - the graph edge type
    All Implemented Interfaces:
    MinimumVertexCoverAlgorithm<V,​E>, MinimumWeightedVertexCoverAlgorithm<V,​E>

    public class BarYehudaEvenTwoApproxVCImpl<V,​E>
    extends java.lang.Object
    implements MinimumWeightedVertexCoverAlgorithm<V,​E>
    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!