Package com.jgalgo.alg.match

Class MatchingCardinalityGabow1976

java.lang.Object
com.jgalgo.alg.match.MatchingAlgoAbstract
com.jgalgo.alg.match.MatchingAlgoAbstractCardinality
com.jgalgo.alg.match.MatchingCardinalityGabow1976
All Implemented Interfaces:
MatchingAlgo
public class MatchingCardinalityGabow1976 extends MatchingAlgoAbstractCardinality
Gabow's implementation of Endmond's algorithm for cardinality maximum matching in general graphs.

The algorithm runs \(n\) iterations, in each one the matching is increased by one. In each iteration, a BFS is run from the unmatched vertices using only alternating paths, searching for an augmenting path. When a blossom is detected, the algorithm contract it to a 'super vertex' and continue in the BFS. Instead of storing the blossom explicitly as stated in the paper, we use UnionFind to implicitly represent the blossoms. Each iteration require \(O(m n \cdot \alpha (m, n))\) time, where \(\alpha (\cdot, \cdot)\) is inverse Ackermann's function.

Based on 'An Efficient Implementation of Edmonds Algorithm for Maximum Matching on Graphs' by Harold N. Gabow (1976). Although the original paper stated the running time is \(O(n^3)\), we implement it using UnionFind, and the running time is \(O(m n \alpha (m, n))\).

Author:
Barak Ugav

  • Constructor Details

    • MatchingCardinalityGabow1976

      public MatchingCardinalityGabow1976()
      Create a new maximum matching object.