English
 
User Manual Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Journal Article

Implementation of O(nmlog n) Weighted Matchings in General Graphs: 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. (2002). Implementation of O(nmlog n) Weighted Matchings in General Graphs: The Power of Data Structures. Journal of Experimental Algorithmics, 7: 4. doi:10.1145/944618.944622.


Cite as: http://hdl.handle.net/11858/00-001M-0000-000F-2FB5-F
Abstract
We describe the implementation of an algorithm which solves the weighted matching problem in general graphs with $n$ vertices and $m$ edges in time $O(nm \log n)$. Our algorithm is a variant of the algorithm of Galil, Micali and Gabow [Galil et al., 1986, SIAM J. Computing, 15, 120--130] and extensively uses sophisticated data structures, in particular \emph{concatenable priority queues}, so as to reduce the time needed to perform dual adjustments and to find tight edges in Edmonds' blossom-shrinking algorithm. We compare our implementation to the experimentally fastest implementation, named \emph{Blossom IV}, due to Cook and Rohe [Cook and Rohe, Technical Report 97863, Forschungsinstitut f{\"u}r Diskrete Mathematik, Universit{\"a}t Bonn]. Blossom IV requires only very simple data structures and has an asymptotic running time of $O(n^2m)$. Our experiments show that our new implementation is superior to Blossom IV. A closer inspection reveals that the running time of Edmonds' blossom-shrinking algorithm in practice heavily depends on the time spent to perform dual adjustments and to find tight edges. Therefore, optimizing these operations, as is done in our implementation, indeed speeds-up the practical performance of implementations of Edmonds' algorithm.