Class EdgeBasedTwoApproxVCImpl<V,​E>

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

    public class EdgeBasedTwoApproxVCImpl<V,​E>
    extends Object
    implements VertexCoverAlgorithm<V>
    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
    Author:
    Linda Buisman
    • Constructor Detail

      • EdgeBasedTwoApproxVCImpl

        public EdgeBasedTwoApproxVCImpl​(Graph<V,​E> graph)
        Constructs a new EdgeBasedTwoApproxVCImpl instance
        Parameters:
        graph - input graph