Weighted maximum matching in general graphs

Version 1.1.0.0 (11,4 KB) von Daniel Saunders
Computes a maximum-weighted matching in a general undirected graph.
4.5
(2)
1,9K Downloads
Aktualisiert 16. Aug 2015

Lizenz anzeigen

Computes a maximum-weighted matching in a general undirected graph. There is the option to only consider maximum-cardinality matching.
Originally written by Joris van Rantwijk in Python:

http://jorisvr.nl/maximummatching.html

Ported to MATLAB, with permission (and not optimized, e.g. for modularity), by Daniel R. Saunders, 2013. BSD license. http://danielrsaunders.com. Original header follows:

The algorithm is taken from "Efficient Algorithms for Finding Maximum Matching in Graphs" by Zvi Galil, ACM Computing Surveys, 1986. It is based on the "blossom" method for finding augmenting paths and the "primal-dual" method for finding a matching of maximum weight, both due to Jack Edmonds.
Some ideas came from "Implementation of algorithms for maximum matching on non-bipartite graphs" by H.J. Gabow, Standford Ph.D. thesis, 1973.

A C program for maximum weight matching by Ed Rothberg was used extensively to validate this new code.

Zitieren als

Daniel Saunders (2026). Weighted maximum matching in general graphs (https://de.mathworks.com/matlabcentral/fileexchange/42827-weighted-maximum-matching-in-general-graphs), MATLAB Central File Exchange. Abgerufen.

Kompatibilität der MATLAB-Version
Erstellt mit R2008b
Kompatibel mit allen Versionen
Plattform-Kompatibilität
Windows macOS Linux
Kategorien
Mehr zu Undirected Graphs finden Sie in Help Center und MATLAB Answers
Tags Tags hinzufügen

Version Veröffentlicht Versionshinweise
1.1.0.0

Fixed a bug that caused certain test cases to return suboptimal matches. Thanks to Jan and to Francesco Betti Sorbelli!
1.0.0.0