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:
VertexCoverAlgorithm<V>
public class ClarksonTwoApproxVCImpl<V,E> extends java.lang.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
-
-
Nested Class Summary
-
Nested classes/interfaces inherited from interface org.jgrapht.alg.interfaces.VertexCoverAlgorithm
VertexCoverAlgorithm.VertexCover<V>, VertexCoverAlgorithm.VertexCoverImpl<V>
-
-
Constructor Summary
Constructors Constructor Description ClarksonTwoApproxVCImpl(Graph<V,E> graph)
Constructs a new ClarksonTwoApproxVCImpl instance where all vertices have uniform weights.ClarksonTwoApproxVCImpl(Graph<V,E> graph, java.util.Map<V,java.lang.Double> vertexWeightMap)
Constructs a new ClarksonTwoApproxVCImpl instance
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description VertexCoverAlgorithm.VertexCover<V>
getVertexCover()
Computes a vertex cover.
-
-
-
Method Detail
-
getVertexCover
public VertexCoverAlgorithm.VertexCover<V> getVertexCover()
Description copied from interface:VertexCoverAlgorithm
Computes a vertex cover.- Specified by:
getVertexCover
in interfaceVertexCoverAlgorithm<V>
- Returns:
- a vertex cover
-
-