Module org.jgrapht.core
Package org.jgrapht.alg.vertexcover

Class ClarksonTwoApproxVCImpl<V,​E>

  • Type Parameters:
    V - the graph vertex type
    E - the graph edge type
    All Implemented Interfaces:
    VertexCoverAlgorithm<V>
    public class ClarksonTwoApproxVCImpl<V,​E>
extends Object
implements VertexCoverAlgorithm<V>
    Implementation of the 2-opt algorithm for a minimum weighted vertex cover by Clarkson, Kenneth L. "A modification of the greedy algorithm for vertex cover." Information Processing Letters 16.1 (1983): 23-25. The solution is guaranteed to be within $2$ times the optimum solution. Runtime: $O(|E|\log |V|)$ Note: this class supports pseudo-graphs
    Author:
    Joris Kinable

    • Constructor Detail

      • ClarksonTwoApproxVCImpl

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

      • ClarksonTwoApproxVCImpl

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