org.jgrapht.alg.vertexcover

## Class EdgeBasedTwoApproxVCImpl<V,E>

• Type Parameters:
`V` - the graph vertex type
`E` - the graph edge type
All Implemented Interfaces:
MinimumVertexCoverAlgorithm<V,E>

```public class EdgeBasedTwoApproxVCImpl<V,E>
extends 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
Author:
Linda Buisman

• ### Nested classes/interfaces inherited from interface org.jgrapht.alg.interfaces.MinimumVertexCoverAlgorithm

`MinimumVertexCoverAlgorithm.VertexCover<V>, MinimumVertexCoverAlgorithm.VertexCoverImpl<V>`
• ### Constructor Summary

Constructors
Constructor and Description
`EdgeBasedTwoApproxVCImpl()`
• ### Method Summary

All Methods
Modifier and Type Method and Description
`MinimumVertexCoverAlgorithm.VertexCover<V>` `getVertexCover(UndirectedGraph<V,E> graph)`
Finds a 2-approximation for a minimal vertex cover of the specified graph.
• ### Methods inherited from class java.lang.Object

`clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`
• ### Constructor Detail

• #### EdgeBasedTwoApproxVCImpl

`public EdgeBasedTwoApproxVCImpl()`
• ### 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 by `BarYehudaEvenTwoApproxVCImpl` or `ClarksonTwoApproxVCImpl`.

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 interface `MinimumVertexCoverAlgorithm<V,E>`
Parameters:
`graph` - the graph
Returns:
a set of vertices which is a vertex cover for the specified graph.