matchpairs function in r2019a
17 Ansichten (letzte 30 Tage)
Ältere Kommentare anzeigen
Lingyao Meng
am 2 Mai 2019
Kommentiert: Mingxing
am 8 Okt. 2021
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 Kommentare
Akzeptierte Antwort
Christine Tobler
am 2 Mai 2019
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 Kommentare
Steven Lord
am 2 Mai 2019
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
am 8 Okt. 2021
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.
Weitere Antworten (0)
Siehe auch
Kategorien
Mehr zu Sparse Matrices finden Sie in Help Center und File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!