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:

MinimumVertexCoverAlgorithm<V,E>, MinimumWeightedVertexCoverAlgorithm<V,E>

public class ClarksonTwoApproxVCImpl<V,E>
extends 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

Author:

Joris Kinable

Nested Class Summary

Nested classes/interfaces inherited from interface org.jgrapht.alg.interfaces.MinimumVertexCoverAlgorithm

MinimumVertexCoverAlgorithm.VertexCover<V>, MinimumVertexCoverAlgorithm.VertexCoverImpl<V>

Constructor Summary

Constructors

Constructor and Description
ClarksonTwoApproxVCImpl()

Method Summary

Modifier and Type	Method and Description
MinimumVertexCoverAlgorithm.VertexCover<V>	getVertexCover(UndirectedGraph<V,E> graph, Map<V,Double> vertexWeightMap) Computes a vertex cover; the weight of each vertex is provided in the in the vertexWeightMap.

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

Constructor Detail

ClarksonTwoApproxVCImpl

public ClarksonTwoApproxVCImpl()

Method Detail

getVertexCover

public MinimumVertexCoverAlgorithm.VertexCover<V> getVertexCover(UndirectedGraph<V,E> graph,
                                                                 Map<V,Double> vertexWeightMap)

Description copied from interface: MinimumWeightedVertexCoverAlgorithm

Computes a vertex cover; the weight of each vertex is provided in the in the vertexWeightMap.

Specified by:

getVertexCover in interface MinimumWeightedVertexCoverAlgorithm<V,E>

Parameters:

graph - the input graph

vertexWeightMap - map containing non-negative weights for each vertex

Returns:

a vertex cover