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

Class ClarksonTwoApproxVCImpl<V,E>

java.lang.Object
org.jgrapht.alg.vertexcover.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 Details

    • 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

  • Method Details