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

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