Home News About Us Contact Contributors Disclaimer Help FAQ

Home
Search
Quick Search
Advanced
Fulltext
Browse
Collections
Persons
My eDoc
Session History
Login
Name:
Password:
Documentation
Help
Support Wiki
Direct access to
document ID:


          Display Documents



ID: 518092.0, MPI für Informatik / Algorithms and Complexity Group
Parallel Shortest Path for Arbitrary Graphs
Authors:Meyer, Ulrich; Sanders, Peter
Language:English
Publisher:Springer
Place of Publication:Berlin, Germany
Date of Publication (YYYY-MM-DD):2000
Title of Proceedings:Euro-Par 2000 Parallel Processing, Proceedings of the 6th International Euro-Par Conference (Euro-Par-00)
Start Page:461
End Page:470
Title of Series:Lecture Notes in Computer Science
Place of Conference/Meeting:Munich, Germany
(Start) Date of Conference/Meeting
 (YYYY-MM-DD):
2000
Audience:Experts Only
Intended Educational Use:No
Abstract / Description: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.
Last Change of the Resource (YYYY-MM-DD):2010-03-02
External Publication Status:published
Document Type:Conference-Paper
Communicated by:Kurt Mehlhorn
Affiliations:MPI für Informatik/Algorithms and Complexity Group
Identifiers:LOCALID:C1256428004B93B8-AE95B3A730DF9050C125695A0043F53D-...
ISBN:3-540-67956-1
The scope and number of records on eDoc is subject to the collection policies defined by each institute - see "info" button in the collection browse view.