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: 518171.0, MPI für Informatik / Algorithms and Complexity Group
Heaps are better than Buckets: Parallel Shortest Paths on Unbalanced Graphs
Authors:Meyer, Ulrich
Language:English
Publisher:Springer
Place of Publication:Berlin, Germany
Date of Publication (YYYY-MM-DD):2001
Title of Proceedings:Proceedings of the 7th International Euro-Par Conference on Parallel Processing (Euro-Par-01) :
Start Page:343
End Page:351
Title of Series:Lecture Notes in Computer Science
Place of Conference/Meeting:Manchester, UK
(Start) Date of Conference/Meeting
 (YYYY-MM-DD):
2001
Audience:Experts Only
Intended Educational Use:No
Abstract / Description: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.
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-83D946724E1284E1C1256A69004811A7-...
URL:http://link.springer.de/link/service/series/0558/p...
ISBN:3-540-42495-4
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.