MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Mehlhorn, Kurt
Schäfer, Guido		dblp
dblp
Editor(s):
Näher, Stefan
Wagner, Dorothea		dblp
dblp
BibTeX cite key*:
Mehlhorn-Schaefer:WeightedMatchings
Title, Booktitle
Title*:
Implementation of $O(nm \log n)$ weighted matchings: The power of data structures
154.pdf (278.23 KB)
Booktitle*:
4th International Workshop on Algorithm Engineering
Event, URLs
Conference URL::
http://www.mpi-sb.mpg.de/~conf2000/wae2000/
Downloading URL:
Event Address*:
Saarbrücken, Germany
Language:
English
Event Date*
(no longer used):
September, 5-8
Organization:
Event Start Date:
Incorrect data type for operator or @Function: Time/Date expected Incorrect data type for operator or @Function: Time/Date expected Incorrect data type for operator or @Function: Time/Date expected
Event End Date:
Incorrect data type for operator or @Function: Time/Date expected Incorrect data type for operator or @Function: Time/Date expected Incorrect data type for operator or @Function: Time/Date expected
Publisher
Name*:
Springer
URL:
http://www.springer-ny.com/
Address*:
New York, USA
Type:
Vol, No, Year, pp.
Series:
Lecture Notes in Computer Science
Volume:
1982
Number:
Month:
Pages:
23-38
Year*:
2000
VG Wort Pages:
ISBN/ISSN:
3-540-42512-8
Sequence Number:
DOI:
Note, Abstract, ©
(LaTeX) 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.
Download
Access Level:
Public

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



BibTeX Entry:

@INPROCEEDINGS{Mehlhorn-Schaefer:WeightedMatchings,
AUTHOR = {Mehlhorn, Kurt and Sch{\"a}fer, Guido},
 EDITOR = {N{\"a}her, Stefan and Wagner, Dorothea},
 TITLE = {Implementation of ${O}(nm \log n)$ weighted matchings: The power of data structures},
 BOOKTITLE = {4th International Workshop on Algorithm Engineering},
 PUBLISHER = {Springer},
 YEAR = {2000},
 VOLUME = {1982},
 PAGES = {23--38},
 SERIES = {Lecture Notes in Computer Science},
 ADDRESS = {Saarbr{\"u}cken, Germany},
 ISBN = {3-540-42512-8},
}

Entry last modified by Tamara Hausmann, 03/02/2010
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Ingrid Finkler		Created
01/22/2001 12:16:33
Revisions
5.
4.
3.
2.
1.		Editor(s)
Tamara Hausmann
Christine Kiesel
Guido Schäfer
Guido Schäfer
Guido Schäfer		Edit Dates
20.06.2006 11:52:16
26.08.2003 16:11:36
05/07/2003 01:18:27 PM
05/02/2002 16:49:51
05/02/2002 16:47:09