de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch

Hilfe Wegweiser Datenschutzhinweis Impressum Kontakt

# Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Konferenzbeitrag

#### Heaps are better than Buckets: Parallel Shortest Paths on Unbalanced Graphs

##### MPG-Autoren
http://pubman.mpdl.mpg.de/cone/persons/resource/persons45038

Meyer,  Ulrich
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

##### Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
##### Volltexte (frei zugänglich)
Es sind keine frei zugänglichen Volltexte verfügbar
##### Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
##### Zitation

Meyer, U. (2001). Heaps are better than Buckets: Parallel Shortest Paths on Unbalanced Graphs. In R. Sakellariou, J. Keane, J. Gurd, & L. Freeman (Eds.), Proceedings of the 7th International Euro-Par Conference on Parallel Processing (Euro-Par-01): (pp. 343-351). Berlin, Germany: Springer.

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.