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 typeE
- 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
-
-
Nested Class Summary
-
Nested classes/interfaces inherited from interface org.jgrapht.alg.interfaces.MinimumVertexCoverAlgorithm
MinimumVertexCoverAlgorithm.VertexCover<V>, MinimumVertexCoverAlgorithm.VertexCoverImpl<V>
-
-
Field Summary
Fields Modifier and Type Field Description private static int
vertexCounter
-
Constructor Summary
Constructors Constructor Description ClarksonTwoApproxVCImpl()
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description MinimumVertexCoverAlgorithm.VertexCover<V>
getVertexCover(UndirectedGraph<V,E> graph, java.util.Map<V,java.lang.Double> vertexWeightMap)
Computes a vertex cover; the weight of each vertex is provided in the in thevertexWeightMap
.-
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
-
Methods inherited from interface org.jgrapht.alg.interfaces.MinimumWeightedVertexCoverAlgorithm
getVertexCover
-
-
-
-
Method Detail
-
getVertexCover
public MinimumVertexCoverAlgorithm.VertexCover<V> getVertexCover(UndirectedGraph<V,E> graph, java.util.Map<V,java.lang.Double> vertexWeightMap)
Description copied from interface:MinimumWeightedVertexCoverAlgorithm
Computes a vertex cover; the weight of each vertex is provided in the in thevertexWeightMap
.- Specified by:
getVertexCover
in interfaceMinimumWeightedVertexCoverAlgorithm<V,E>
- Parameters:
graph
- the input graphvertexWeightMap
- map containing non-negative weights for each vertex- Returns:
- a vertex cover
-
-