|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: INNER | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Object | +--org._3pq.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
Constructor Summary | |
VertexCovers()
|
Method Summary | |
java.util.Set |
find2ApproximationCover(Graph g)
Finds a 2-approximation for a minimal vertex cover of the specified graph. |
java.util.Set |
findGreedyCover(UndirectedGraph 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 java.util.Set find2ApproximationCover(Graph 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 java.util.Set findGreedyCover(UndirectedGraph 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 GraphHelper.undirectedGraph(Graph)
or AsUndirectedGraph
.
g
- the graph for which vertex cover approximation is to be found.
|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: INNER | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |