Electronic Journal Article @Article Zeitschriftenartikel in einem e-Journal

 Show entries of: this year (2019) | last year (2018) | two years ago (2017) | Notes URL
 Action: login to update Options: Goto entry point

 Author, Editor
 Author(s): Mehlhorn, Kurt Schäfer, Guido dblp dblp
 BibTeX cite key*: MS2002

 Title
 Title*: Implementation of $O(nm \log n)$ Weighted Matchings in General Graphs: The Power of Data Structures

 Journal
 Journal Title*: Journal of Experimental Algorithmics Journal's URL: http://www.jea.acm.org/ Download URL for the article: http://www.jea.acm.org/2002/MehlhornMatching/ Language: English

 Publisher
 Publisher's Name: ACM Publisher's URL: http://www.acm.org/ Publisher's Address: New York, USA ISSN: 1084-6654

 Vol, No, Year, pp.
 Volume: 7 Number: Month: Year*: 2002 Pages: Number of VG Pages: Sequence Number: 4 DOI: 10.1145/944618.944622

 Note: (LaTeX) 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. URL for the Abstract: Categories / Keywords: General Matching, Weighted Matching, Edmonds' Algorithm HyperLinks / References / URLs: http://dblp.uni-trier.de/db/journals/jea/jea7.html#MehlhornS02 Copyright Message: Personal Comments: Download Access Level: Intranet

 Correlation
 MPG Unit: Max-Planck-Institut für Informatik MPG Subunit: Algorithms and Complexity Group Audience: Expert Appearance: MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort

BibTeX Entry:

@MISC{MS2002,
AUTHOR = {Mehlhorn, Kurt and Sch{\"a}fer, Guido},
TITLE = {Implementation of ${O}(nm \log n)$ Weighted Matchings in General Graphs: The Power of Data Structures},
BOOKTITLE = {Proceedings of the n?th Conference on},
JOURNAL = {Journal of Experimental Algorithmics},
PUBLISHER = {ACM},
YEAR = {2002},
VOLUME = {7},
SERIES = {Lecture Notes in Computer Science},