Maximum Cardinality matching

constructs a (non-weighted) maximum cardinality matching

Description

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)

• MATLAB release: MATLAB 6.0 (R12)

[Nick]

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

[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