matchpairs function in r2019a
조회 수: 17 (최근 30일)
이전 댓글 표시
I used matchpairs function to solve linear assignment problem but was wondering which algorithm it implemented and the time complexity. Is it Hungarian?
Thank you
댓글 수: 0
채택된 답변
Christine Tobler
2019년 5월 2일
The algorithm solves the same problem as the Hungarian algorithm, but it's not the same algorithm. The Hungarian algorithm has complexity O(N^4), while the algorithm used here has complexity O(N^3*log(N)) for dense matrices, and O(nnz*N*log(N)) for sparse matrices.
These are worst-case complexities, for many matrices the performance will be better, as simple cases are treated in a preprocessing step.
If you type 'edit matchpairs', there is a reference to a paper describing the algorithm used in that file.
댓글 수: 3
Steven Lord
2019년 5월 2일
The paper is also listed in the References section of the documentation page for matchpairs. That way you avoid the chance of accidentally modifying matchpairs.m.
Mingxing
2021년 10월 8일
Thanks for your answer. I checked the algorithm file of 'matchpairs' and I found that there is a 'matlab.internal.graph.perfectMatching' function to perform matching (no further explainations). I am wondering what exactly it is.
And I also checked the reference paper, the paper actually gave several algorithms.
추가 답변 (0개)
참고 항목
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!