Package com.jgalgo.alg.cover

Class EdgeCoverCardinality

java.lang.Object
com.jgalgo.alg.cover.EdgeCoverAbstract
com.jgalgo.alg.cover.EdgeCoverCardinality
All Implemented Interfaces:
EdgeCover
public class EdgeCoverCardinality extends EdgeCoverAbstract
A simply algorithm for computing a minimum edge cover using a maximum matching algorithm.

The algorithm compute a maximum cardinality matching and adds the matching edges to the cover, and then adds more edges greedily until the cover is complete. This algorithm achieves the optimal solution for both directed and undirected graphs. For directed graph, the algorithm treat use the undirected view of the graph.

The algorithm running time is dominated by the maximum matching algorithm. Other than that, the algorithm use linear time and space.

Author:
Barak Ugav

  • Constructor Details

    • EdgeCoverCardinality

      public EdgeCoverCardinality()
      Create a new edge cover algorithm object for unweighted graphs.

      Please prefer using EdgeCover.newInstance() to get a default implementation for the EdgeCover interface.