de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch
 
Hilfe Wegweiser Impressum Kontakt Einloggen
  DetailsucheBrowse

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.


Zitierlink: http://hdl.handle.net/11858/00-001M-0000-000F-3192-4
Zusammenfassung
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.