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):
Sakellariou, Rizos
Keane, John
Gurd, John
Freeman, Len
dblp
dblp
dblp
dblp
BibTeX cite key*:
Meyer2001c
Title, Booktitle
Title*:
Heaps are better than Buckets: Parallel Shortest Paths on Unbalanced Graphs
Booktitle*:
Proceedings of the 7th International Euro-Par Conference on Parallel Processing (Euro-Par-01) :
Event, URLs
Conference URL::
http://europar.man.ac.uk/
Downloading URL:
http://link.springer.de/link/service/series/0558/papers/2150/21500343.pdf
Event Address*:
Manchester, UK
Language:
English
Event Date*
(no longer used):
August, 28 - August, 31
Organization:
Event Start Date:
5 December 2021
Event End Date:
5 December 2021
Publisher
Name*:
Springer
URL:
http://www.springer.de/
Address*:
Berlin, Germany
Type:
Vol, No, Year, pp.
Series:
Lecture Notes in Computer Science
Volume:
2150
Number:
Month:
August
Pages:
343-351
Year*:
2001
VG Wort Pages:
15
ISBN/ISSN:
3-540-42495-4
Sequence Number:
DOI:
Note, Abstract, ©
(LaTeX) Abstract:
We propose a new parallel algorithm for the
single-source shortest-path problem (SSSP). Its
heap data structure is particularly advantageous on graphs with
a moderate number of high degree nodes.
On arbitrary directed graphs with
$n$ nodes, $m$ edges and independent random edge weights
uniformly distributed in the range $[0,1]$ and maximum
shortest path weight $\Diam$ the PRAM version of our algorithm runs in
${\cal O}(\log^2 n \cdot \min_{i} \{2^i \cdot \Diam \cdot \log n+ |V_i| \})$
average-case time using ${\cal O}(n \cdot \log n +m )$ operations
where $|V_i|$ is the number of graph vertices with degree at least $2^i$.
For power-law graph models of the Internet or call graphs
this results in the first work-efficient $o(n^{1/4})$ average-case time algorithm.
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, VG Wort



BibTeX Entry:

@INPROCEEDINGS{Meyer2001c,
AUTHOR = {Meyer, Ulrich},
EDITOR = {Sakellariou, Rizos and Keane, John and Gurd, John and Freeman, Len},
TITLE = {Heaps are better than Buckets: Parallel Shortest Paths on Unbalanced Graphs},
BOOKTITLE = {Proceedings of the 7th International Euro-Par Conference on Parallel Processing (Euro-Par-01) :},
PUBLISHER = {Springer},
YEAR = {2001},
VOLUME = {2150},
PAGES = {343--351},
SERIES = {Lecture Notes in Computer Science},
ADDRESS = {Manchester, UK},
MONTH = {August},
ISBN = {3-540-42495-4},
}


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
06/12/2001 03:07:11 PM
Revisions
7.
6.
5.
4.
3.
Editor(s)
Uwe Brahm
Anja Becker
Ulrich Meyer
Ulrich Meyer
Ulrich Meyer
Edit Dates
04/25/2002 07:47:46 PM
08.04.2002 14:33:13
08/01/2002 11:22:09
03/09/2001 13:34:47
18/07/2001 14:56:38