Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


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



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

URL of the conference:

http://www.mpi-sb.mpg.de/~conf2000/wae2000/

URL for downloading the paper:


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
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)
Ingrid Finkler
Created
01/22/2001 12:16:33 PM
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
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section
154.pdf
View attachments here: