MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Meyer, Ulrich
Sanders, Peter		dblp
dblp
Editor(s):
Bilardi, Gianfranco
Italiano, Giuseppe F.
Pietracaprina, Andrea
Pucci, Geppino		dblp
dblp
dblp
dblp
BibTeX cite key*:
MeyerSanders1998a
Title, Booktitle
Title*:
$\Delta$-Stepping: A Parallel Single Source Shortest Path Algorithm
Booktitle*:
Proceedings of the 6th Annual European Symposium on Algorithms (ESA-98)
Event, URLs
Conference URL::
http://www.dsi.unive.it/~esa98/
Downloading URL:
Event Address*:
Venice, Italy
Language:
English
Event Date*
(no longer used):
August, 24 - 26
Organization:
Event Start Date:
22 September 2023
Event End Date:
22 September 2023
Publisher
Name*:
Springer
URL:
Address*:
Berlin, Germany
Type:
Vol, No, Year, pp.
Series:
Lecture Notes in Computer Science
Volume:
1461
Number:
Month:
August
Pages:
393-404
Year*:
1998
VG Wort Pages:
ISBN/ISSN:
3-540-64848-8
Sequence Number:
DOI:
Note, Abstract, ©
(LaTeX) Abstract:
In spite of intensive research, little progress has been
made towards fast and work-efficient parallel algorithms for the
single source shortest path problem. Our \emph{$\Delta$-stepping
algorithm}, a generalization of Dial's algorithm and the Bellman-Ford
algorithm, improves this situation at least in the following
``average-case'' sense:
For random directed graphs with edge probability $\frac{d}{n}$
and uniformly distributed edge weights a PRAM version works in
expected time ${\cal O}(\log^3 n/\log\log n)$ using linear work.

The algorithm also allows for efficient adaptation to
distributed memory machines. Implementations show that
our approach works on real machines.
As a side effect, we get a simple linear time sequential
algorithm for a large class of not necessarily random
directed graphs with random edge weights.
Keywords:
Parallel Computation, Single Source Shortest Path, Graph Algorithms, Random Graphs
HyperLinks / References / URLs:
http://www.mpi-sb.mpg.de/~umeyer/
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



BibTeX Entry:

@INPROCEEDINGS{MeyerSanders1998a,
AUTHOR = {Meyer, Ulrich and Sanders, Peter},
 EDITOR = {Bilardi, Gianfranco and Italiano, Giuseppe F. and Pietracaprina, Andrea and Pucci, Geppino},
 TITLE = {$\Delta$-Stepping: A Parallel Single Source Shortest Path Algorithm},
 BOOKTITLE = {Proceedings of the 6th Annual European Symposium on Algorithms (ESA-98)},
 PUBLISHER = {Springer},
 YEAR = {1998},
 VOLUME = {1461},
 PAGES = {393--404},
 SERIES = {Lecture Notes in Computer Science},
 ADDRESS = {Venice, Italy},
 MONTH = {August},
 ISBN = {3-540-64848-8},
}

Entry last modified by Evelyn Haak, 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 16:12:36
Revisions
5.
4.
3.
2.
1.		Editor(s)
Evelyn Haak
Uwe Brahm
Uwe Brahm
Ulrich Meyer
Ulrich Meyer		Edit Dates
01/04/99 13:09:02
29.03.99 18:33:19
29.03.99 18:32:42
20/09/98 16:15:00
07/09/98 16:34:15