Package org.jgrapht.alg.vertexcover
Class EdgeBasedTwoApproxVCImpl<V,E>
- java.lang.Object
-
- org.jgrapht.alg.vertexcover.EdgeBasedTwoApproxVCImpl<V,E>
-
- Type Parameters:
V
- the graph vertex typeE
- the graph edge type
- All Implemented Interfaces:
MinimumVertexCoverAlgorithm<V,E>
public class EdgeBasedTwoApproxVCImpl<V,E> extends java.lang.Object implements MinimumVertexCoverAlgorithm<V,E>
Finds a 2-approximation for a minimum vertex cover 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 Note: this class supports pseudo-graphs- Since:
- Nov 6, 2003
-
-
Nested Class Summary
-
Nested classes/interfaces inherited from interface org.jgrapht.alg.interfaces.MinimumVertexCoverAlgorithm
MinimumVertexCoverAlgorithm.VertexCover<V>, MinimumVertexCoverAlgorithm.VertexCoverImpl<V>
-
-
Constructor Summary
Constructors Constructor Description EdgeBasedTwoApproxVCImpl()
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description MinimumVertexCoverAlgorithm.VertexCover<V>
getVertexCover(UndirectedGraph<V,E> graph)
Finds a 2-approximation for a minimal vertex cover of the specified graph.
-
-
-
Method Detail
-
getVertexCover
public MinimumVertexCoverAlgorithm.VertexCover<V> getVertexCover(UndirectedGraph<V,E> graph)
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. Note: this class supports pseudo-graphs Runtime: O(|E|) Albeit the fact that this is a 2-approximation algorithm for vertex cover, its results are often of lower quality than the results produced byBarYehudaEvenTwoApproxVCImpl
orClarksonTwoApproxVCImpl
.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.
- Specified by:
getVertexCover
in interfaceMinimumVertexCoverAlgorithm<V,E>
- Parameters:
graph
- the graph- Returns:
- a set of vertices which is a vertex cover for the specified graph.
-
-