Package org.jgrapht.alg.interfaces
Interface MinimumWeightedVertexCoverAlgorithm<V,E>
-
- Type Parameters:
V
- the graph vertex typeE
- the graph edge type
- All Superinterfaces:
MinimumVertexCoverAlgorithm<V,E>
- All Known Implementing Classes:
BarYehudaEvenTwoApproxVCImpl
,ClarksonTwoApproxVCImpl
,GreedyVCImpl
,RecursiveExactVCImpl
public interface MinimumWeightedVertexCoverAlgorithm<V,E> extends MinimumVertexCoverAlgorithm<V,E>
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.
-
-
Nested Class Summary
-
Nested classes/interfaces inherited from interface org.jgrapht.alg.interfaces.MinimumVertexCoverAlgorithm
MinimumVertexCoverAlgorithm.VertexCover<V>, MinimumVertexCoverAlgorithm.VertexCoverImpl<V>
-
-
Method Summary
All Methods Instance Methods Abstract Methods Default Methods Modifier and Type Method Description default MinimumVertexCoverAlgorithm.VertexCover<V>
getVertexCover(UndirectedGraph<V,E> graph)
Computes a vertex cover; all vertices are considered to have equal weight.MinimumVertexCoverAlgorithm.VertexCover<V>
getVertexCover(UndirectedGraph<V,E> graph, java.util.Map<V,java.lang.Double> vertexWeightMap)
Computes a vertex cover; the weight of each vertex is provided in the in thevertexWeightMap
.
-
-
-
Method Detail
-
getVertexCover
default MinimumVertexCoverAlgorithm.VertexCover<V> getVertexCover(UndirectedGraph<V,E> graph)
Computes a vertex cover; all vertices are considered to have equal weight.- Specified by:
getVertexCover
in interfaceMinimumVertexCoverAlgorithm<V,E>
- Parameters:
graph
- the graph- Returns:
- a vertex cover
-
getVertexCover
MinimumVertexCoverAlgorithm.VertexCover<V> getVertexCover(UndirectedGraph<V,E> graph, java.util.Map<V,java.lang.Double> vertexWeightMap)
Computes a vertex cover; the weight of each vertex is provided in the in thevertexWeightMap
.- Parameters:
graph
- the input graphvertexWeightMap
- map containing non-negative weights for each vertex- Returns:
- a vertex cover
-
-