Package com.jgalgo.alg.match

Class MatchingWeightedGabow1990

java.lang.Object

com.jgalgo.alg.match.MatchingAlgoAbstract

com.jgalgo.alg.match.MatchingAlgoAbstractBasedMaximum

com.jgalgo.alg.match.MatchingWeightedGabow1990

All Implemented Interfaces:

MatchingAlgo

public class MatchingWeightedGabow1990
extends MatchingAlgoAbstractBasedMaximum

Edmonds' Blossom algorithm for Maximum weighted matching with Gabow's dynamic LCA data structure.

This algorithm runs in \(O(m n + n^2 \log n)\) time and uses linear space.

Based on the original paper 'Paths, Trees, and Flowers' by Jack Edmonds (1965), later improved by 'An Efficient Implementation of Edmonds Algorithm for Maximum Matching on Graphs' by Harold N. Gabow (1976), and using the efficient dynamic LCA from 'Data Structures for Weighted Matching and Nearest Common Ancestors with Linking' by Harold N. Gabow (1990) resulting in the final running time.

Author:

Barak Ugav

Nested Class Summary

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

MatchingAlgo.Builder

Constructor Summary

Constructors

Constructor	Description
MatchingWeightedGabow1990()	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

MatchingWeightedGabow1990

public MatchingWeightedGabow1990()

Create a new maximum weighted matching object.