public class VertexCovers
extends java.lang.Object
Constructor and Description |
---|
VertexCovers() |
Modifier and Type | Method and Description |
---|---|
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.
|
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.