File Exchange

image thumbnail

Maximum Cardinality matching

version 1.2 (3.55 KB) by

constructs a (non-weighted) maximum cardinality matching

2 Downloads

Updated

View License

If you use this code please kindly cite the following paper

"Structure induction by lossless graph compression"
Leonid Peshkin, In Proc. of Data Compression Conf. DCC , 2007

[mate] = card_match(adj) constructs a (Non-weighted) maximum cardinality matching
on a graph represented by ADJ-acency matrix with edge IDs as elements
OUTPUT: mate(i) = j means edge (i,j)=(j,i) belongs to the matching.

REMARKs:
a vertex _v_ is called "outer" when there is an alternating path from _v_ to
an unmatched vertex _u_ that starts with a matched edge.

MATLAB implementation of H. Gabow's labelling scheme explaned in JACM 23, pp221-34
by Dr. Leonid Peshkin MIT AI Lab Dec 2003 [inspired by Ed Rothberg C code Jun 1985]
http://www.csail.mit.edu/~pesha
sample ADJ matrix for the following graph: (2)---(1)---(3)
1 2 3 4-edge(1,2)
1 0 4 5
2 4 0 0 5-edge(1,3)
3 5 0 0
we assume no isolated vertices and un-directed graph (symmetric ADJ)

Comments and Ratings (2)

Leon Peshkin

If you use this code please kindly cite the following paper

"Structure induction by lossless graph compression"
Leonid Peshkin
In Proc. of Data Compression Conf. DCC , 2007

Nick

Nick (view profile)

this falls right into place - very happy to have found it, thanks !

Updates

1.2

modified description

MATLAB Release
MATLAB 6.0 (R12)

Download apps, toolboxes, and other File Exchange content using Add-On Explorer in MATLAB.

» Watch video

Win prizes and improve your MATLAB skills

Play today