New in Version 7.2
1. Maximum Cardinality Matching in General Graphs
The default implementation of the MAX_CARD_MATCHING function
(see User Manual Section 10.8.) has been replaced by an
implementation of a new algorithm by H.N. Gabow :
The Weighted Matching Approach to Maximum Cardinality Matching
A detailed description of the implementation is given in the paper
Gabow's Cardinality Matching Algorithm in General Graphs:
Implementation and Experiments
by Matin Ansaripour, Alireza Danaei and Kurt Mehlhorn.
The previous implementation, based on the original blossom-shrinking
algorithm by Edmonds/Gabow, is still available as
MAX_CARD_MATCHING_EDMONDS
and a variant using a heuristic suggested by J. Kececioglu and J. Pecquer
as
MAX_CARD_MATCHING_KECECIOGLU
see here
The new algorithm by Gabow can also be called explicitely as
MAX_CARD_MATCHING_GABOW.
Compile and run the program
LEDAROOT/app/speed/mc_matching.cpp
for a comparison of the efficiency of the different matching algorithms.
This program can also be started from the online demo page
leda.uni-trier.de/leda/demos?speed/mc_matching