Package com.jgalgo.alg.match

Class MatchingWeightedBipartiteHungarianMethod

java.lang.Object
com.jgalgo.alg.match.MatchingAlgoAbstract
com.jgalgo.alg.match.MatchingAlgoAbstractBasedMaximum
com.jgalgo.alg.match.MatchingWeightedBipartiteHungarianMethod
All Implemented Interfaces:
MatchingAlgo
public class MatchingWeightedBipartiteHungarianMethod extends MatchingAlgoAbstractBasedMaximum
Kuhn's Hungarian method for maximum weighted matching in bipartite graphs.

The running time of the algorithm is \(O(m n + n^2 \log n)\) and it uses linear space.

Based on 'The Hungarian method for the assignment problem' by Kuhn, H.W. (1955). The original paper stated a running time of \(O(n^3)\), but by using heaps with decreaseKey operations in \(O(1)\) the running time can be reduced to \(O(m n + n^2 \log n)\), as done in this implementation.

Author:
Barak Ugav

  • Constructor Details

    • MatchingWeightedBipartiteHungarianMethod

      public MatchingWeightedBipartiteHungarianMethod()
      Create a new maximum weighted matching object.