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

Hilfe Wegweiser Impressum Kontakt Einloggen

# Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Konferenzbeitrag

#### $\Delta$-Stepping: A Parallel Single Source Shortest Path Algorithm

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

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

http://pubman.mpdl.mpg.de/cone/persons/resource/persons45344

Sanders,  Peter
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., & Sanders, P. (1998). $\Delta$-Stepping: A Parallel Single Source Shortest Path Algorithm. In G. Bilardi, G. F. Italiano, A. Pietracaprina, & G. Pucci (Eds.), Proceedings of the 6th Annual European Symposium on Algorithms (ESA-98) (pp. 393-404). Berlin, Germany: Springer.

In spite of intensive research, little progress has been made towards fast and work-efficient parallel algorithms for the single source shortest path problem. Our \emph{$\Delta$-stepping algorithm}, a generalization of Dial's algorithm and the Bellman-Ford algorithm, improves this situation at least in the following average-case'' sense: For random directed graphs with edge probability $\frac{d}{n}$ and uniformly distributed edge weights a PRAM version works in expected time ${\cal O}(\log^3 n/\log\log n)$ using linear work. The algorithm also allows for efficient adaptation to distributed memory machines. Implementations show that our approach works on real machines. As a side effect, we get a simple linear time sequential algorithm for a large class of not necessarily random directed graphs with random edge weights.