English
 
User Manual Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Conference Paper

Implementation of O(nmlog n) Weighted Matchings: The Power of Data Structures

MPS-Authors
/persons/resource/persons45021

Mehlhorn,  Kurt
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons45363

Schäfer,  Guido
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Ressource
No external resources are shared
Fulltext (public)
There are no public fulltexts stored in PuRe
Supplementary Material (public)
There is no public supplementary material available
Citation

Mehlhorn, K., & Schäfer, G. (2000). Implementation of O(nmlog n) Weighted Matchings: The Power of Data Structures. In S. Näher, & D. Wagner (Eds.), Algorithm Engineering (pp. 23-38). Berlin: Springer. doi:10.1007/3-540-44691-5_3.


Cite as: http://hdl.handle.net/11858/00-001M-0000-000F-335D-E
Abstract
We describe the implementation of an $O(nm \log n)$ algorithm for weighted matchings in general graphs. The algorithm is a variant of the algorithm of Galil, Micali, and Gabow and requires the use of concatenable priority queues. No previous implementation had a worst-case guarantee of $O(nm \log n)$. We compare our implementation to the experimentally fastest implementation (called Blossom IV) due to Cook and Rohe; Blossom IV is an implementation of Edmonds' algorithm and has a running time no better than $O(n^3)$. Blossom IV requires only very simple data structures. Our experiments show that our new implementation is competitive to Blossom IV.