

PREV CLASS NEXT CLASS  FRAMES NO FRAMES  
SUMMARY: NESTED  FIELD  CONSTR  METHOD  DETAIL: FIELD  CONSTR  METHOD 
java.lang.Object org.jscience.computing.graph.algorithms.VertexCovers
public 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 NPComplete 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 2approximation 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, CMPU240: 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 edgedirections are ignored. To ignore edge
directions you can use GraphHelper.undirectedGraph(Graph)
or org.jscience.computing.graph.graph.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 