org.jgrapht.alg

Class VertexCovers

java.lang.Object

org.jgrapht.alg.VertexCovers

Deprecated.

@Deprecated
public abstract class VertexCovers
extends Object

Algorithms to find a vertex cover for a graph. 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

Since:

Nov 6, 2003

Author:

Linda Buisman

Constructor Summary

Constructors

Constructor and Description
VertexCovers() Deprecated.

Method Summary

Modifier and Type	Method and Description
static <V,E> Set<V>	find2ApproximationCover(Graph<V,E> g) Deprecated. Use EdgeBasedTwoApproxVCImpl, ClarksonTwoApproxVCImpl, or BarYehudaEvenTwoApproxVCImpl instead.
static <V,E> Set<V>	findGreedyCover(UndirectedGraph<V,E> g) Deprecated. use GreedyVCImpl instead.

Methods inherited from class java.lang.Object

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

Constructor Detail

VertexCovers

public VertexCovers()

Deprecated.

Method Detail

find2ApproximationCover

@Deprecated
public static <V,E> Set<V> find2ApproximationCover(Graph<V,E> g)

Deprecated. Use EdgeBasedTwoApproxVCImpl, ClarksonTwoApproxVCImpl, or BarYehudaEvenTwoApproxVCImpl instead.

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.

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.

Type Parameters:

V - the graph vertex type

E - the graph edge type

Parameters:

g - the graph for which vertex cover approximation is to be found.

Returns:

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

findGreedyCover

@Deprecated
public static <V,E> Set<V> findGreedyCover(UndirectedGraph<V,E> g)

Deprecated. use GreedyVCImpl instead.

Finds a greedy approximation for a minimal vertex cover of a specified graph. At each iteration, the algorithm picks the vertex with the highest degree and adds it to the cover, until all edges are covered.

The algorithm works on undirected graphs, but can also work on directed graphs when their edge-directions are ignored. To ignore edge directions you can use Graphs.undirectedGraph(Graph) or AsUndirectedGraph.

Type Parameters:

V - the graph vertex type

E - the graph edge type

Parameters:

g - the graph for which vertex cover approximation is to be found.

Returns:

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