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:








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

Abstract, Links, (C)

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},
ADDRESS = {?},
ISBN = {1084-6654},
DOI = {10.1145/944618.944622},
}


Entry last modified by Anja Becker, 03/02/2010
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
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)
Guido Schäfer
Created
04/14/2003 02:26:44 PM
Revisions
15.
14.
13.
12.
11.
Editor(s)
Anja Becker
Christine Kiesel
Christine Kiesel
Christine Kiesel
Christine Kiesel
Edit Dates
04.01.2008 16:03:39
29.09.2006 15:04:07
11.09.2003 15:56:44
11.09.2003 15:50:30
11.09.2003 15:47:45