Class ClarksonTwoApproxVCImpl<V,​E>

  • Type Parameters:
    V - the graph vertex type
    E - the graph edge type
    All Implemented Interfaces:

    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
    Joris Kinable
    • Constructor Detail

      • ClarksonTwoApproxVCImpl

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

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