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):





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

URL of the conference:

http://www.ipdps.org/ipdps2002/

URL for downloading the paper:


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
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
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

Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section