org.jgrapht.alg

Class 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 Detail

• VertexCovers

public VertexCovers()
Deprecated.
• Method Detail

• find2ApproximationCover

@Deprecated
public static <V,E> Set<V> find2ApproximationCover(Graph<V,E> g)
Deprecated.
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)