Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:








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:

15 September 2019

Event End Date:

15 September 2019

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
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
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