matchpairs function in r2019a
17 visualizaciones (últimos 30 días)
Mostrar comentarios más antiguos
Lingyao Meng
el 2 de Mayo de 2019
Comentada: Mingxing
el 8 de Oct. de 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 comentarios
Respuesta aceptada
Christine Tobler
el 2 de Mayo de 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 comentarios
Steven Lord
el 2 de Mayo de 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
el 8 de Oct. de 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.
Más respuestas (0)
Ver también
Categorías
Más información sobre Sparse Matrices en Help Center y File Exchange.
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!