Maximum Cardinality matching

버전 1.2.0.0 (3.55 KB) 작성자: Leon Peshkin
constructs a (non-weighted) maximum cardinality matching
다운로드 수: 1.9K
업데이트 날짜: 2009/5/28

라이선스 보기

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 릴리스 호환 정보
개발 환경: R12
모든 릴리스와 호환
플랫폼 호환성
Windows macOS Linux
카테고리
Help CenterMATLAB Answers에서 Directed Graphs에 대해 자세히 알아보기

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!
버전 게시됨 릴리스 정보
1.2.0.0

modified description

1.0.0.0