Package com.jgalgo.alg.match

Class MatchingWeightedBlossomV

java.lang.Object

com.jgalgo.alg.match.MatchingAlgoAbstract

com.jgalgo.alg.match.MatchingAlgoAbstractBasedMinimum

com.jgalgo.alg.match.MatchingWeightedBlossomV

All Implemented Interfaces:

MatchingAlgo

public class MatchingWeightedBlossomV
extends MatchingAlgoAbstractBasedMinimum

Blossom V implementation for maximum weighted matching.

The implementation is based on 'Blossom V: A new implementation of a minimum cost perfect matching algorithm' by Vladimir Kolmogorov. It is an implementation of Edmonds 'Blossom' algorithm, using priory queues (ReferenceableHeap, pairing heaps) to find the next tight edge each iteration. In contrast to MatchingWeightedGabow1990, it achieve a worse \(O(n^3 m)\) running time in the worst case, but runs faster in practice.

The implementation actually computes minimum perfect matching, and assume such perfect matching always exists. Maximum or non-perfect matchings are computed by a reduction to a minimum perfect matching instance.

Author:

Barak Ugav

Nested Class Summary

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

MatchingAlgo.Builder

Constructor Summary

Constructors

Constructor	Description
MatchingWeightedBlossomV()	Create a new minimum 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

MatchingWeightedBlossomV

public MatchingWeightedBlossomV()

Create a new minimum weighted matching object.