Maximum Cardinality matching
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)
인용 양식
Leon Peshkin (2025). Maximum Cardinality matching (https://kr.mathworks.com/matlabcentral/fileexchange/23159-maximum-cardinality-matching), MATLAB Central File Exchange. 검색 날짜: .
MATLAB 릴리스 호환 정보
플랫폼 호환성
Windows macOS Linux카테고리
태그
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!