Package com.jgalgo.alg.cover

Class VertexCoverAbstract

java.lang.Object
com.jgalgo.alg.cover.VertexCoverAbstract
All Implemented Interfaces:
VertexCover
Direct Known Subclasses:
VertexCoverBarYehuda
public abstract class VertexCoverAbstract extends Object implements VertexCover
Abstract class for computing a minimum vertex cover.

The class implements the interface by solving the problem on the index graph and then maps the results back to the original graph. The implementation for index graphs is abstract and left to the subclasses.

Author:
Barak Ugav

  • Constructor Details

    • VertexCoverAbstract

      public VertexCoverAbstract()
      Default constructor.

  • Method Details

    • computeMinimumVertexCover

      public <V, E> Set<V> computeMinimumVertexCover(Graph<V,E> g, WeightFunction<V> w)
      Description copied from interface: VertexCover
      Compute a minimum vertex cover of a graph with respect to a vertex weight function.

      Note that finding the minimum vertex cover is an NP-hard problem, therefore the result of this function is an approximation of the optimal solution.

      If g is IntGraph, the returned object is IntSet. If g is IntGraph, prefer to pass IWeightFunction as w to avoid boxing/unboxing.

      Specified by:
      computeMinimumVertexCover in interface VertexCover
      Type Parameters:
      V - the vertices type
      E - the edges type
      Parameters:
      g - a graph
      w - a vertex weight function
      Returns:
      a minimum vertex cover