Class EdgeBasedTwoApproxVCImpl<V,E>

java.lang.Object
org.jgrapht.alg.vertexcover.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 Details

    • EdgeBasedTwoApproxVCImpl

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