Class EdgeBasedTwoApproxVCImpl<V,​E>

  • Type Parameters:
    V - the graph vertex type
    E - the graph edge type
    All Implemented Interfaces:
    MinimumVertexCoverAlgorithm<V,​E>

    public class EdgeBasedTwoApproxVCImpl<V,​E>
    extends java.lang.Object
    implements MinimumVertexCoverAlgorithm<V,​E>
    Finds a 2-approximation for a minimum vertex cover A vertex cover is a set of vertices that touches all the edges in the graph. The graph's vertex set is a trivial cover. However, a minimal vertex set (or at least an approximation for it) is usually desired. Finding a true minimal vertex cover is an NP-Complete problem. For more on the vertex cover problem, see http://mathworld.wolfram.com/VertexCover.html Note: this class supports pseudo-graphs
    Since:
    Nov 6, 2003