Code covered by the BSD License  

Highlights from
Weighted maximum matching in general graphs

5.0
5.0 | 1 rating Rate this file 39 Downloads (last 30 days) File Size: 12.3 KB File ID: #42827 Version: 1.0
image thumbnail

Weighted maximum matching in general graphs

by

 

Computes a maximum-weighted matching in a general undirected graph.

| Watch this File

File Information
Description

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.

Required Products MATLAB
MATLAB release MATLAB 7.7 (R2008b)
Tags for This File   Please login to tag files.
Please login to add a comment or rating.
Comments and Ratings (1)
09 May 2015 Ameer Mansour

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

Contact us