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):
Bode, Arndt
Ludwig, Thomas
Karl, Wolfgang
Wismüller, Roland		dblp
dblp
dblp
dblp
BibTeX cite key*:
MeySan2000
Title, Booktitle
Title*:
Parallel Shortest Path for Arbitrary Graphs
Booktitle*:
Euro-Par 2000 Parallel Processing, Proceedings of the 6th International Euro-Par Conference (Euro-Par-00)
Event, URLs
Conference URL::
http://wwwbode.informatik.tu-muenchen.de/~europar/
Downloading URL:
Event Address*:
Munich, Germany
Language:
English
Event Date*
(no longer used):
August, 29 - September, 1
Organization:
Event Start Date:
21 September 2023
Event End Date:
21 September 2023
Publisher
Name*:
Springer
URL:
Address*:
Berlin, Germany
Type:
Vol, No, Year, pp.
Series:
Lecture Notes in Computer Science
Volume:
1900
Number:
Month:
August
Pages:
461-470
Year*:
2000
VG Wort Pages:
20
ISBN/ISSN:
3-540-67956-1
Sequence Number:
DOI:
Note, Abstract, ©
(LaTeX) Abstract:
In spite of intensive research, no work-efficient parallel algorithm
for the single source shortest path problem is known which works in
sublinear time for arbitrary directed graphs with non-negative edge
weights. We present an algorithm that improves this situation
for graphs where the ratio $\Diam/\Delta$ between the maximum weight
of a shortest path $\Diam$ and a ``safe step width''
$\Delta$ is not too large.
We show how such a step width can be found efficiently and
give several graph classes which meet the above condition, such that
our parallel shortest path algorithm runs in sublinear time and uses linear
work.
The new algorithm is even faster than a previous one which only works
for random graphs with random edge weights.
On those graphs our new approach is faster
by a factor of $\Th{\log n/\log\log n}$ and achieves an expected
time bound of $\Oh{\log^2 n}$ using linear work.
Keywords:
graph algorithms, shortest path, PRAM, parallel
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{MeySan2000,
AUTHOR = {Meyer, Ulrich and Sanders, Peter},
 EDITOR = {Bode, Arndt and Ludwig, Thomas and Karl, Wolfgang and Wism{\"u}ller, Roland},
 TITLE = {Parallel Shortest Path for Arbitrary Graphs},
 BOOKTITLE = {Euro-Par 2000 Parallel Processing, Proceedings of the 6th International Euro-Par Conference (Euro-Par-00)},
 PUBLISHER = {Springer},
 YEAR = {2000},
 VOLUME = {1900},
 PAGES = {461--470},
 SERIES = {Lecture Notes in Computer Science},
 ADDRESS = {Munich, Germany},
 MONTH = {August},
 ISBN = {3-540-67956-1},
}

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)
Ulrich Meyer		Created
09/14/2000 14:22:16
Revisions
5.
4.
3.
2.
1.		Editor(s)
Uwe Brahm
Anja Becker
Anja Becker
Peter Sanders
Peter Sanders		Edit Dates
05/02/2001 11:17:09 AM
20.03.2001 17:01:08
14.03.2001 13:10:31
23/01/2001 20:37:32
14/09/2000 14:27:23