org.jgrapht.alg.interfaces

## Interface VertexCoverAlgorithm<V>

• Type Parameters:
V - vertex type
All Known Implementing Classes:
BarYehudaEvenTwoApproxVCImpl, ClarksonTwoApproxVCImpl, EdgeBasedTwoApproxVCImpl, GreedyVCImpl, RecursiveExactVCImpl

public interface VertexCoverAlgorithm<V>
Computes a (weighted) 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. Consequently, any algorithm designed for the weighted version of the problem can also solve instances of the unweighted version.
Author:
Joris Kinable
• ### Nested Class Summary

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

All Methods
Modifier and Type Method and Description
VertexCoverAlgorithm.VertexCover<V> getVertexCover()
Computes a vertex cover.
• ### Method Detail

• #### getVertexCover

VertexCoverAlgorithm.VertexCover<V> getVertexCover()
Computes a vertex cover.
Returns:
a vertex cover