Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT
 
 
DownloadE-Mail
 Lokale TagsFreigabegeschichteDetailsÜbersicht
  A Parallelization of Dijkstra's Shortest Path Algorithm

Crauser, A., Mehlhorn, K., Meyer, U., & Sanders, P. (1998). A Parallelization of Dijkstra's Shortest Path Algorithm. In L. Brim, J. Gruska, & J. Zlatuška (Eds.), Mathematical Foundations of Computer Science 1998 (pp. 722-731). Berlin, Germany: Springer. doi:10.1007/BFb0055823.

Item is

 

einblenden: alle ausblenden: alle

Basisdaten

einblenden: ausblenden:
Datensatz-Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-372F-7 Versions-Permalink: https://hdl.handle.net/11858/00-001M-0000-002B-508F-3
Genre: Konferenzbeitrag
Latex : A Parallelization of {D}ijkstra's Shortest Path Algorithm

Dateien

einblenden: Dateien
ausblenden: Dateien
:
Mehlhorn136.pdf (Verlagsversion), 673KB
 
Datei-Permalink:
-
Name:
Mehlhorn136.pdf
Beschreibung:
-
OA-Status:
Sichtbarkeit:
Privat
MIME-Typ / Prüfsumme:
application/pdf
Technische Metadaten:
Copyright Datum:
-
Copyright Info:
-
Lizenz:
-

Externe Referenzen

einblenden:

Urheber

einblenden:
ausblenden:
 Urheber:
Crauser, Andreas1, Autor           
Mehlhorn, Kurt1, Autor           
Meyer, Ulrich1, Autor           
Sanders, Peter1, Autor           
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Inhalt

einblenden:
ausblenden:
Schlagwörter: -
 Zusammenfassung: The single source shortest path (SSSP) problem lacks parallel solutions which are fast and simultaneously work-efficient. We propose simple criteria which divide Dijkstra's sequential SSSP algorithm into a number of phases, such that the operations within a phase can be done in parallel. We give a PRAM algorithm based on these criteria and analyze its performance on random digraphs with random edge weights uniformly distributed in $[0,1]$. We use the ${\cal G}(n,d/n)$ model: the graph consists of $n$~nodes and each edge is chosen with probability $d/n$. Our PRAM algorithm needs ${\cal O}(n^{1/3} \log n)$ time and ${\cal O}(n \log n+dn)$ work with high probability (whp). We also give extensions to external memory computation. Simulations show the applicability of our approach even on non-random graphs.

Details

einblenden:
ausblenden:
Sprache(n): eng - English
 Datum: 2008-01-212006-05-281998
 Publikationsstatus: Erschienen
 Seiten: -
 Ort, Verlag, Ausgabe: -
 Inhaltsverzeichnis: -
 Art der Begutachtung: -
 Identifikatoren: eDoc: 344426
BibTex Citekey: CMMS1998a
DOI: 10.1007/BFb0055823
 Art des Abschluß: -

Veranstaltung

einblenden:
ausblenden:
Titel: 23rd International Symposium on the Mathematical Foundations of Computer Science
Veranstaltungsort: Brno, Czech Republic
Start-/Enddatum: 1998-08-24 - 1998-08-28

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle 1

einblenden:
ausblenden:
Titel: Mathematical Foundations of Computer Science 1998
  Kurztitel : MFCS 1998
  Untertitel : 23rd International Symposium, MFCS'98 ; Brno, Czech Republic, August 24-28, 1998 ; Proceedings
Genre der Quelle: Konferenzband
 Urheber:
Brim, Luboš1, Herausgeber
Gruska, Jozef1, Herausgeber
Zlatuška, Jiří, Herausgeber
Affiliations:
1 External Organizations, ou_persistent22            
Ort, Verlag, Ausgabe: Berlin, Germany : Springer
Seiten: - Band / Heft: - Artikelnummer: - Start- / Endseite: 722 - 731 Identifikator: ISBN: 3-540-64827-5

Quelle 2

einblenden:
ausblenden:
Titel: Lecture Notes in Computer Science
Genre der Quelle: Reihe
 Urheber:
Affiliations:
Ort, Verlag, Ausgabe: -
Seiten: - Band / Heft: 1450 Artikelnummer: - Start- / Endseite: - Identifikator: -