Package org.jgrapht.alg.interfaces
Interface MinimumVertexCoverAlgorithm<V,E>
-
- Type Parameters:
V
- the graph vertex typeE
- 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.
-
-
Nested Class Summary
Nested Classes Modifier and Type Interface Description static interface
MinimumVertexCoverAlgorithm.VertexCover<V>
A vertex coverstatic class
MinimumVertexCoverAlgorithm.VertexCoverImpl<V>
Default implementation of a vertex cover
-
Method Summary
All Methods Instance Methods Abstract Methods Modifier and Type Method Description MinimumVertexCoverAlgorithm.VertexCover<V>
getVertexCover(UndirectedGraph<V,E> graph)
Computes a vertex cover; all vertices are considered to have equal weight.
-
-
-
Method Detail
-
getVertexCover
MinimumVertexCoverAlgorithm.VertexCover<V> getVertexCover(UndirectedGraph<V,E> graph)
Computes a vertex cover; all vertices are considered to have equal weight.- Parameters:
graph
- the graph- Returns:
- a vertex cover
-
-