MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Meyer, Ulrichdblp
Editor(s):
BibTeX cite key*:
Meyer2002a
Title, Booktitle
Title*:
Buckets Strike Back: Improved Parallel Shortest-Paths
Booktitle*:
International Parallel and Distributed Processing Symposium (IPDPS-02)
Event, URLs
Conference URL::
http://www.ipdps.org/ipdps2002/
Downloading URL:
Event Address*:
Fort Lauderdale, USA
Language:
English
Event Date*
(no longer used):
-- April, 15 - April, 19
Organization:
IEEE
Event Start Date:
15 April 2002
Event End Date:
19 April 2002
Publisher
Name*:
IEEE
URL:
Address*:
Los Alamitos, USA
Type:
Vol, No, Year, pp.
Series:
Volume:
Number:
Month:
April
Pages:
75-75
Year*:
2002
VG Wort Pages:
15
ISBN/ISSN:
0-7695-1573-8
Sequence Number:
DOI:
Note, Abstract, ©
Note:
The proceedings book only contains the paper abstracts. The
full papers are on a CD.
(LaTeX) Abstract:
We study the average-case complexity of
the parallel single-source shortest-path (SSSP) problem,
assuming arbitrary directed graphs with $n$ nodes, $m$ edges,
and independent random edge weights uniformly distributed in
$[0,1]$. We provide a new bucket-based parallel SSSP algorithm that runs in
$T={\cal O}(\log^2 n \cdot \min_{i} \{2^i \cdot \Diam + |V_i| \})$
average-case time using ${\cal O}(n +m+T)$ work on a
PRAM where $\Diam$ denotes the
maximum shortest-path weight and $|V_i|$ is
the number of graph vertices with in-degree at least $2^i$.
All previous algorithms either required more time or more work.
The minimum performance gain is a logarithmic factor improvement; on
certain graph classes, accelerations by factors of more than $n^{0.4}$
can be achieved.
Keywords:
Parallel Algorithms, Shortest-Paths, Average-Case Analysis
Download
Access Level:
Public

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, VG Wort



BibTeX Entry:

@INPROCEEDINGS{Meyer2002a,
AUTHOR = {Meyer, Ulrich},
TITLE = {Buckets Strike Back: Improved Parallel Shortest-Paths},
BOOKTITLE = {International Parallel and Distributed Processing Symposium (IPDPS-02)},
PUBLISHER = {IEEE},
YEAR = {2002},
ORGANIZATION = {IEEE},
PAGES = {75--75},
ADDRESS = {Fort Lauderdale, USA},
MONTH = {April},
ISBN = {0-7695-1573-8},
}


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
04/23/2002 06:15:27 PM
Revisions
2.
1.
0.

Editor(s)
Uwe Brahm
Christine Kiesel
Ulrich Meyer

Edit Dates
10/22/2003 04:01:36 PM
28.08.2003 15:49:54
23/04/2002 18:15:28