MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Crauser, Andreas
Mehlhorn, Kurt
Meyer, Ulrich
Sanders, Peter
dblp
dblp
dblp
dblp
Editor(s):
Brim, Lubos
Gruska, Jozef
Zlatuska, Jiri
dblp
dblp
dblp
BibTeX cite key*:
CMMS1998a
Title, Booktitle
Title*:
A Parallelization of Dijkstra's Shortest Path Algorithm
Booktitle*:
Proceedings of the 23rd International Symposium on the Mathematical Foundations of Computer Science (MFCS-98)
Event, URLs
Conference URL::
http://www.fi.muni.cz/mfcs98/
Downloading URL:
Event Address*:
Brno, Czech Republic
Language:
English
Event Date*
(no longer used):
August, 24 - August, 28
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:
Address*:
Berlin, Germany
Type:
Vol, No, Year, pp.
Series:
Lecture Notes in Computer Science
Volume:
1450
Number:
Month:
August
Pages:
722-731
Year*:
1998
VG Wort Pages:
ISBN/ISSN:
3-540-64827-5
Sequence Number:
DOI:
10.1007/BFb0055823
Note, Abstract, ©
(LaTeX) Abstract:
The single source shortest path (SSSP) problem
lacks parallel solutions which are fast and simultaneously
work-efficient.
We propose simple criteria which divide
Dijkstra's sequential SSSP algorithm into a number of phases,
such that the operations within a phase can be done
in parallel. We give a PRAM algorithm based on these criteria
and analyze its performance on random digraphs
with random edge weights uniformly distributed in $[0,1]$.
We use the ${\cal G}(n,d/n)$ model: the graph consists of
$n$~nodes and each edge is chosen with probability $d/n$.
Our PRAM algorithm needs ${\cal O}(n^{1/3} \log n)$
time and ${\cal O}(n \log n+dn)$ work with high probability (whp).
We also give extensions to external memory computation.

Simulations show the applicability of our approach
even on non-random graphs.
URL for the Abstract:
http://link.springer.de/link/service/series/0558/bibs/1450/14500722.htm
Keywords:
Parallel Computation, Single Source Shortest Path, PRAM, random graphs, external memory
HyperLinks / References / URLs:
http://www.mpi-sb.mpg.de/~umeyer/
http://dblp.uni-trier.de/db/conf/mfcs/mfcs98.html#CrauserMMS98
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



BibTeX Entry:

@INPROCEEDINGS{CMMS1998a,
AUTHOR = {Crauser, Andreas and Mehlhorn, Kurt and Meyer, Ulrich and Sanders, Peter},
EDITOR = {Brim, Lubos and Gruska, Jozef and Zlatuska, Jiri},
TITLE = {A Parallelization of Dijkstra's Shortest Path Algorithm},
BOOKTITLE = {Proceedings of the 23rd International Symposium on the Mathematical Foundations of Computer Science (MFCS-98)},
PUBLISHER = {Springer},
YEAR = {1998},
VOLUME = {1450},
PAGES = {722--731},
SERIES = {Lecture Notes in Computer Science},
ADDRESS = {Brno, Czech Republic},
MONTH = {August},
ISBN = {3-540-64827-5},
DOI = {10.1007/BFb0055823},
}


Entry last modified by Anja Becker, 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)
Ulrich Meyer
Created
09/07/1998 05:20:32 PM
Revisions
6.
5.
4.
3.
2.
Editor(s)
Anja Becker
Christine Kiesel
Evelyn Haak
Uwe Brahm
Uwe Brahm
Edit Dates
21.01.2008 10:05:07
28.08.2006 13:56:09
01/04/99 12:29:12
29.03.99 18:58:36
29.03.99 18:28:50