Journal Article
@Article
Artikel in Fachzeitschrift

Show entries of:

this year (2022) | last year (2021) | two years ago (2020) | Notes URL

Action:

login to update
Options:








Author, Editor(s)
Author(s):
Bast, Holger
Mehlhorn, Kurt
Schäfer, Guido
Tamaki, Hisao		dblp
dblp
dblp
dblp

BibTeX cite key*:

BMST03

Title

Title*:

A Heuristic for Dijkstra's Algorithm With Many Targets and its Use in Weighted Matching Algorithms

Journal

Journal Title*:

Algorithmica
Journal's URL:

http://link.springer.de/link/service/journals/00453/

Download URL
for the article:

http://springerlink.metapress.com/openurl.asp?genre=article&issn=0178-4617&volume=36&issue=1&spage=75
http://dx.doi.org/10.1007/s00453-002-1008-z
http://link.springer.de/link/service/journals/00453/contents/02/1008/index.html
Language:

English

Publisher

Publisher's
Name:

Springer
Publisher's URL:


Publisher's
Address:

Berlin, Germany
ISSN:


Vol, No, pp, Date

Volume*:

36
Number:

1

Publishing Date:

2003

Pages*:

75-88
Number of
VG Pages:


Page Start:


Page End:


Sequence Number:


DOI:

10.1007/s00453-002-1008-z

Note, Abstract, ©

Note:


(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 12 was achieved.
We also present a partial analysis that gives some theoretical support for our
experimental findings.

URL for the Abstract:


Categories,
Keywords:

single-source shortest-path problem, Dijkstra's algorithm, weighted bipartite matching problem, assignment problem

HyperLinks / References / URLs:

http://dblp.uni-trier.de/db/journals/algorithmica/algorithmica36.html#BastMS03

Copyright Message:


Personal Comments:


Download
Access Level:

Intranet

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


BibTeX Entry:

@ARTICLE{BMST03,
AUTHOR = {Bast, Holger and Mehlhorn, Kurt and Sch{\"a}fer, Guido and Tamaki, Hisao},
 TITLE = {A Heuristic for {Dijkstra's} Algorithm With Many Targets and its Use in Weighted Matching Algorithms},
 JOURNAL = {Algorithmica},
 PUBLISHER = {Springer},
 YEAR = {2003},
 NUMBER = {1},
 VOLUME = {36},
 PAGES = {75--88},
 ADDRESS = {Berlin, Germany},
 DOI = {10.1007/s00453-002-1008-z},
}

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/09/2003 06:58:56 PM
Revisions
8.
7.
6.
5.
4.		Editor(s)
Anja Becker
Christine Kiesel
Christine Kiesel
Tamara Hausmann
Tamara Hausmann		Edit Dates
07.01.2008 09:15:28
03.10.2006 20:55:58
03.10.2006 20:54:19
20.06.2006 11:45:40
06/17/2004 10:23:37 AM