Package com.jgalgo.alg.match

Class 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 Detail

      • MatchingCardinalityGabow1976

        public MatchingCardinalityGabow1976()
        Create a new maximum matching object.