\input zb-basic
\input zb-ioport
\iteman{io-port 01863286}
\itemau{Meyer, Ulrich}
\itemti{Heaps are better than buckets: Parallel shortest paths on unbalanced graphs.}
\itemso{Sakellariou, Rizos (ed.) et al., Euro-Par 2001 Parallel processing. 7th international Euro-Par conference, Manchester, GB, August 28-31, 2001. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 2150, 343-351 (2001).}
\itemab
Summary: 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 ${\cal L}$ the PRAM version of our algorithm runs in ${\cal O}(\log^2 n \cdot \min_{i} \{2^i \cdot {\cal L}\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.
\itemrv{~}
\itemcc{}
\itemut{}
\itemli{http://link.springer.de/link/service/series/0558/bibs/2150/21500343}
\end