Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop
Show entries of:
this year
(2020) |
last year
(2019) |
two years ago
(2018) |
Notes URL
Action:
login to update
Options:
Goto entry point
Author, Editor
Author(s):
Meyer, Ulrich
dblp
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
URL of the conference:
http://europar.man.ac.uk/
URL for downloading the paper:
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:
29 September 2020
Event End Date:
29 September 2020
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
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