Module org.jgrapht.core

Package 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:

VertexCoverAlgorithm<V>

public class EdgeBasedTwoApproxVCImpl<V,E>
extends java.lang.Object
implements VertexCoverAlgorithm<V>

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

Author:

Linda Buisman

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
EdgeBasedTwoApproxVCImpl(Graph<V,E> graph)	Constructs a new EdgeBasedTwoApproxVCImpl instance

Method Summary

Modifier and Type	Method	Description
VertexCoverAlgorithm.VertexCover<V>	getVertexCover()	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 Details

EdgeBasedTwoApproxVCImpl

public EdgeBasedTwoApproxVCImpl(Graph<V,E> graph)

Constructs a new EdgeBasedTwoApproxVCImpl instance

Parameters:

graph - input graph

Method Details

getVertexCover

public VertexCoverAlgorithm.VertexCover<V> getVertexCover()

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 VertexCoverAlgorithm<V>

Returns:

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