org.jgrapht.alg.vertexcover

Class EdgeBasedTwoApproxVCImpl<V,E>

java.lang.Object

org.jgrapht.alg.vertexcover.EdgeBasedTwoApproxVCImpl<V,E>

Type Parameters:

V - the graph vertex type

E - the graph edge type

All Implemented Interfaces:

MinimumVertexCoverAlgorithm<V,E>

public class EdgeBasedTwoApproxVCImpl<V,E>
extends Object
implements MinimumVertexCoverAlgorithm<V,E>

Finds a 2-approximation for a minimum vertex cover A vertex cover is a set of vertices that touches all the edges in the graph. The graph's vertex set is a trivial cover. However, a minimal vertex set (or at least an approximation for it) is usually desired. Finding a true minimal vertex cover is an NP-Complete problem. For more on the vertex cover problem, see http://mathworld.wolfram.com/VertexCover.html Note: this class supports pseudo-graphs

Since:

Nov 6, 2003

Author:

Linda Buisman

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
EdgeBasedTwoApproxVCImpl()

Method Summary

Modifier and Type	Method and Description
MinimumVertexCoverAlgorithm.VertexCover<V>	getVertexCover(UndirectedGraph<V,E> graph) Finds a 2-approximation for a minimal vertex cover of the specified graph.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

EdgeBasedTwoApproxVCImpl

public EdgeBasedTwoApproxVCImpl()

Method Detail

getVertexCover

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

Finds a 2-approximation for a minimal vertex cover of the specified graph. The algorithm promises a cover that is at most double the size of a minimal cover. The algorithm takes O(|E|) time. Note: this class supports pseudo-graphs Runtime: O(|E|) Albeit the fact that this is a 2-approximation algorithm for vertex cover, its results are often of lower quality than the results produced by BarYehudaEvenTwoApproxVCImpl or ClarksonTwoApproxVCImpl.

For more details see Jenny Walter, CMPU-240: Lecture notes for Language Theory and Computation, Fall 2002, Vassar College, http://www.cs.vassar.edu/~walter/cs241index/lectures/PDF/approx.pdf.

Specified by:

getVertexCover in interface MinimumVertexCoverAlgorithm<V,E>

Parameters:

graph - the graph

Returns:

a set of vertices which is a vertex cover for the specified graph.