File Exchange

image thumbnail

Weighted maximum matching in general graphs

version (11.4 KB) by Daniel Saunders
Computes a maximum-weighted matching in a general undirected graph.


Updated 16 Aug 2015

View Version History

View License

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:

Ported to MATLAB, with permission (and not optimized, e.g. for modularity), by Daniel R. Saunders, 2013. BSD license. 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.

Cite As

Daniel Saunders (2021). Weighted maximum matching in general graphs (, MATLAB Central File Exchange. Retrieved .

Comments and Ratings (3)

Riccardo Iacobucci

Unfortunately the current implementation use global variables and is extremely slow for large instances

HyoJoon Park

How should I interpret the outcome of:
edgeData = [2, 3, 10; 3, 4, 11]
result = maxWeightMatching(edgeData)

which is [-1 -1 4 3]?

Ameer Mansour

but it show me there is error , i am using matlab 2015a

MATLAB Release Compatibility
Created with R2008b
Compatible with any release
Platform Compatibility
Windows macOS Linux

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!