org.jgrapht.alg.interfaces

## Interface MinimumVertexCoverAlgorithm<V,E>

• Type Parameters:
V - the graph vertex type
E - the graph edge type
All Known Subinterfaces:
MinimumWeightedVertexCoverAlgorithm<V,E>
All Known Implementing Classes:
BarYehudaEvenTwoApproxVCImpl, ClarksonTwoApproxVCImpl, EdgeBasedTwoApproxVCImpl, GreedyVCImpl, RecursiveExactVCImpl

public interface MinimumVertexCoverAlgorithm<V,E>
Computes a vertex cover in an undirected graph. A vertex cover of a graph is a set of vertices such that each edge of the graph is incident to at least one vertex in the set. A minimum vertex cover is a vertex cover having the smallest possible number of vertices for a given graph. The size of a minimum vertex cover of a graph G is known as the vertex cover number. A vertex cover of minimum weight is a vertex cover where the sum of weights assigned to the individual vertices in the cover has been minimized. The minimum vertex cover problem is a special case of the minimum weighted vertex cover problem where all vertices have equal weight.
Author:
Joris Kinable
• ### Nested Class Summary

Nested Classes
Modifier and Type Interface and Description
static interface  MinimumVertexCoverAlgorithm.VertexCover<V>
A vertex cover
static class  MinimumVertexCoverAlgorithm.VertexCoverImpl<V>
Default implementation of a vertex cover
• ### Method Summary

All Methods
Modifier and Type Method and Description
MinimumVertexCoverAlgorithm.VertexCover<V> getVertexCover(Graph<V,E> graph)
Computes a vertex cover; all vertices are considered to have equal weight.
• ### Method Detail

• #### getVertexCover

MinimumVertexCoverAlgorithm.VertexCover<V> getVertexCover(Graph<V,E> graph)
Computes a vertex cover; all vertices are considered to have equal weight.
Parameters:
graph - the graph
Returns:
a vertex cover