org._3pq.jgrapht.alg
Class VertexCovers
java.lang.Object
org._3pq.jgrapht.alg.VertexCovers
public class VertexCovers
extends java.lang.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
find2ApproximationCover
public Set find2ApproximationCover(Graph g)
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.
g
- the graph for which vertex cover approximation is to be found.
- a set of vertices which is a vertex cover for the specified
graph.
findGreedyCover
public Set findGreedyCover(UndirectedGraph g)
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
GraphHelper.undirectedGraph(Graph)
or
AsUndirectedGraph
.
g
- the graph for which vertex cover approximation is to be found.
- a set of vertices which is a vertex cover for the specified
graph.