Package org.jgrapht.alg
Class VertexCovers
java.lang.Object
org.jgrapht.alg.VertexCovers
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 -
Method Summary
Modifier and TypeMethodDescriptionstatic <V,
E> Set <V> find2ApproximationCover
(Graph<V, E> g) Finds a 2-approximation for a minimal vertex cover of the specified graph.static <V,
E> Set <V> findGreedyCover
(UndirectedGraph<V, E> g) Finds a greedy approximation for a minimal vertex cover of a specified graph.
-
Constructor Details
-
VertexCovers
public VertexCovers()
-
-
Method Details
-
find2ApproximationCover
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.
- 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
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)
orAsUndirectedGraph
.- 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.
-