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):

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

URL of the conference:

http://www.fi.muni.cz/mfcs98/

URL for downloading the paper:


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
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)
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