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
Sanders, Peter

dblp
dblp



Editor(s):

Bode, Arndt
Ludwig, Thomas
Karl, Wolfgang
Wismüller, Roland

dblp
dblp
dblp
dblp



BibTeX cite key*:

MeySan2000

Title, Booktitle

Title*:

Parallel Shortest Path for Arbitrary Graphs

Booktitle*:

Euro-Par 2000 Parallel Processing, Proceedings of the 6th International Euro-Par Conference (Euro-Par-00)

Event, URLs

URL of the conference:

http://wwwbode.informatik.tu-muenchen.de/~europar/

URL for downloading the paper:


Event Address*:

Munich, Germany

Language:

English

Event Date*
(no longer used):

August, 29 - September, 1

Organization:


Event Start Date:

12 November 2019

Event End Date:

12 November 2019

Publisher

Name*:

Springer

URL:


Address*:

Berlin, Germany

Type:


Vol, No, Year, pp.

Series:

Lecture Notes in Computer Science

Volume:

1900

Number:


Month:

August

Pages:

461-470

Year*:

2000

VG Wort Pages:

20

ISBN/ISSN:

3-540-67956-1

Sequence Number:


DOI:




Note, Abstract, ©


(LaTeX) Abstract:

In spite of intensive research, no work-efficient parallel algorithm
for the single source shortest path problem is known which works in
sublinear time for arbitrary directed graphs with non-negative edge
weights. We present an algorithm that improves this situation
for graphs where the ratio $\Diam/\Delta$ between the maximum weight
of a shortest path $\Diam$ and a ``safe step width''
$\Delta$ is not too large.
We show how such a step width can be found efficiently and
give several graph classes which meet the above condition, such that
our parallel shortest path algorithm runs in sublinear time and uses linear
work.
The new algorithm is even faster than a previous one which only works
for random graphs with random edge weights.
On those graphs our new approach is faster
by a factor of $\Th{\log n/\log\log n}$ and achieves an expected
time bound of $\Oh{\log^2 n}$ using linear work.

Keywords:

graph algorithms, shortest path, PRAM, parallel

HyperLinks / References / URLs:

http://www.mpi-sb.mpg.de/~umeyer/



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



BibTeX Entry:

@INPROCEEDINGS{MeySan2000,
AUTHOR = {Meyer, Ulrich and Sanders, Peter},
EDITOR = {Bode, Arndt and Ludwig, Thomas and Karl, Wolfgang and Wism{\"u}ller, Roland},
TITLE = {Parallel Shortest Path for Arbitrary Graphs},
BOOKTITLE = {Euro-Par 2000 Parallel Processing, Proceedings of the 6th International Euro-Par Conference (Euro-Par-00)},
PUBLISHER = {Springer},
YEAR = {2000},
VOLUME = {1900},
PAGES = {461--470},
SERIES = {Lecture Notes in Computer Science},
ADDRESS = {Munich, Germany},
MONTH = {August},
ISBN = {3-540-67956-1},
}


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
09/14/2000 02:22:16 PM
Revisions
5.
4.
3.
2.
1.
Editor(s)
Uwe Brahm
Anja Becker
Anja Becker
Peter Sanders
Peter Sanders
Edit Dates
05/02/2001 11:17:09 AM
20.03.2001 17:01:08
14.03.2001 13:10:31
23/01/2001 20:37:32
14/09/2000 14:27:23