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

Nested Class Summary

Nested classes/interfaces inherited from interface com.jgalgo.alg.match.MatchingAlgo

MatchingAlgo.Builder

Constructor Summary

Constructors

Constructor	Description
MatchingWeightedBipartiteHungarianMethod()	Create a new maximum weighted matching object.

Method Summary

Methods inherited from class com.jgalgo.alg.match.MatchingAlgoAbstract

computeMaximumMatching, computeMaximumPerfectMatching, computeMinimumMatching, computeMinimumPerfectMatching

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Details

MatchingWeightedBipartiteHungarianMethod

public MatchingWeightedBipartiteHungarianMethod()

Create a new maximum weighted matching object.