|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectorg.jgrapht.alg.VertexCovers
public abstract class 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
Constructor Summary | |
---|---|
VertexCovers()
|
Method Summary | ||
---|---|---|
static
|
find2ApproximationCover(Graph<V,E> g)
Finds a 2-approximation for a minimal vertex cover of the specified graph. |
|
static
|
findGreedyCover(UndirectedGraph<V,E> g)
Finds a greedy approximation for a minimal vertex cover of a specified graph. |
Methods inherited from class java.lang.Object |
---|
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
Constructor Detail |
---|
public VertexCovers()
Method Detail |
---|
public static <V,E> java.util.Set<V> find2ApproximationCover(Graph<V,E> g)
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.
public static <V,E> java.util.Set<V> findGreedyCover(UndirectedGraph<V,E> g)
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
.
g
- the graph for which vertex cover approximation is to be found.
|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |