Code covered by the BSD License  

Highlights from
Maximum Cardinality matching

5.0

5.0 | 1 rating Rate this file 21 Downloads (last 30 days) File Size: 3.55 KB File ID: #23159

Maximum Cardinality matching

by

 

02 Mar 2009 (Updated )

constructs a (non-weighted) maximum cardinality matching

| Watch this File

File Information
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)
Tags for This File   Please login to tag files.
Please login to add a comment or rating.
Comments and Ratings (2)
21 Apr 2009 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

26 Mar 2009 Nick

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

Updates
28 May 2009

modified description

Contact us