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):
Meyer auf der Heide, Friedhelmdblp
BibTeX cite key*:
MehlhornSchaefer2001
Title, Booktitle
Title*:
A Heuristic for Dijkstra's Algorithm With Many Targets and its Use in Weighted Matching Algorithms
Booktitle*:
Proceedings of the 9th Annual European Symposium on Algorithms (ESA-01)
Event, URLs
Conference URL::
http://www.brics.dk/esa2001/
Downloading URL:
http://link.springer.de/link/service/series/0558/papers/2161/21610242.pdf
Event Address*:
Arhus, Denmark
Language:
English
Event Date*
(no longer used):
August, 28-31
Organization:
Event Start Date:
16 April 2021
Event End Date:
16 April 2021
Publisher
Name*:
Springer
URL:
http://www.springer-ny.com/
Address*:
Berlin, Germany
Type:
Vol, No, Year, pp.
Series:
Lecture Notes in Computer Science
Volume:
2161
Number:
Month:
August
Pages:
242-253
Year*:
2001
VG Wort Pages:
ISBN/ISSN:
3-540-42493-8
Sequence Number:
DOI:
Note, Abstract, ©
(LaTeX) Abstract:
We consider the single-source many-targets shortest-path (SSMTSP) problem in
directed graphs with non-negative edge weights. A source node $s$ and a target
set $T$ is specified and the goal is to compute a shortest path from $s$ to a
node in $T$.
Our interest in the shortest path problem with many targets stems from its use
in weighted bipartite matching algorithms. A weighted bipartite matching in a
graph with $n$ nodes on each side reduces to $n$ SSMTSP problems, where the number
of targets varies between $n$ and $1$.

The SSMTSP problem can be solved by Dijkstra's algorithm. We describe a heuristic
that leads to a significant improvement in running time for the weighted matching
problem; in our experiments a speed-up by up to a factor of 10 was achieved.
We also present a partial analysis that gives some theoretical support for our
experimental findings.
Keywords:
single-source shortest-path problem, Dijkstra's algorithm, weighted bipartite matching problem, assignment problem
Download
Access Level:

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



BibTeX Entry:

@INPROCEEDINGS{MehlhornSchaefer2001,
AUTHOR = {Mehlhorn, Kurt and Sch{\"a}fer, Guido},
EDITOR = {Meyer auf der Heide, Friedhelm},
TITLE = {A Heuristic for {Dijkstra's} Algorithm With Many Targets and its Use in Weighted Matching Algorithms},
BOOKTITLE = {Proceedings of the 9th Annual European Symposium on Algorithms (ESA-01)},
PUBLISHER = {Springer},
YEAR = {2001},
VOLUME = {2161},
PAGES = {242--253},
SERIES = {Lecture Notes in Computer Science},
ADDRESS = {Arhus, Denmark},
MONTH = {August},
ISBN = {3-540-42493-8},
}


Entry last modified by Uwe Brahm, 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)
Guido Schäfer
Created
02/05/2002 04:37:14 PM
Revisions
6.
5.
4.
3.
2.
Editor(s)
Uwe Brahm
Uwe Brahm
Uwe Brahm
Anja Becker
Anja Becker
Edit Dates
04/25/2002 09:48:51 PM
04/25/2002 09:46:50 PM
04/25/2002 07:43:05 PM
08.04.2002 15:49:39
08.04.2002 14:42:45