Class ClarksonTwoApproxVCImpl<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 ClarksonTwoApproxVCImpl<V,​E>
    extends java.lang.Object
    implements MinimumWeightedVertexCoverAlgorithm<V,​E>
    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