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.