Package org.jgrapht.alg.vertexcover

Class 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 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!
    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,
                                    java.util.Map<V,​java.lang.Double> vertexWeightMap)
        Constructs a new BarYehudaEvenTwoApproxVCImpl instance
        Parameters:
        graph - input graph
        vertexWeightMap - mapping of vertex weights