Package com.jgalgo.alg.match

Class MatchingWeightedGabow1990Simpler

java.lang.Object

com.jgalgo.alg.match.MatchingAlgoAbstract

com.jgalgo.alg.match.MatchingAlgoAbstractBasedMaximum

com.jgalgo.alg.match.MatchingWeightedGabow1990Simpler

All Implemented Interfaces:

MatchingAlgo

public class MatchingWeightedGabow1990Simpler
extends MatchingAlgoAbstractBasedMaximum

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

This algorithm runs in \(O(m n \log n)\) time and uses linear space. The asymptotically running time is lower than the regular MatchingWeightedGabow1990 implementation, but it runs faster in practice. Instead of using SubtreeMergeFindMin and LowestCommonAncestorDynamic, a simple heap is used to tracker 'blossom' steps.

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
MatchingWeightedGabow1990Simpler()	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

MatchingWeightedGabow1990Simpler

public MatchingWeightedGabow1990Simpler()

Create a new maximum weighted matching object.