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

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Bericht

A simple parallel algorithm for the single-source shortest path problem on planar diagraphs

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

Träff,  Jesper Larsson
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

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

Zaroliagis,  Christos
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
Volltexte (frei zugänglich)

1996-1-012
(beliebiger Volltext), 11KB

Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

Träff, J. L., & Zaroliagis, C.(1996). A simple parallel algorithm for the single-source shortest path problem on planar diagraphs (MPI-I-1996-1-012). Saarbrücken: Max-Planck-Institut für Informatik.


Zitierlink: http://hdl.handle.net/11858/00-001M-0000-0014-A192-8
Zusammenfassung
We present a simple parallel algorithm for the {\em single-source shortest path problem} in {\em planar digraphs} with nonnegative real edge weights. The algorithm runs on the EREW PRAM model of parallel computation in $O((n^{2\epsilon} + n^{1-\epsilon})\log n)$ time, performing $O(n^{1+\epsilon}\log n)$ work for any $0<\epsilon<1/2$. The strength of the algorithm is its simplicity, making it easy to implement, and presumably 474 quite efficient in practice. The algorithm improves upon the work of all previous algorithms. The work can be further reduced to $O(n^{1+\epsilon})$, by plugging in a less practical, sequential planar shortest path algorithm. Our algorithm is based on a region decomposition of the input graph, and uses a well-known parallel implementation of Dijkstra's algorithm.