Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT
 
 
DownloadE-Mail
 Lokale TagsFreigabegeschichteDetailsÜbersicht
  A Goal-Directed Shortest Path Algorithm Using Precomputed Cluster Distances

Maue, J. (2006). A Goal-Directed Shortest Path Algorithm Using Precomputed Cluster Distances. Master Thesis, Universität des Saarlandes, Saarbrücken.

Item is

 

einblenden: alle ausblenden: alle

Basisdaten

einblenden: ausblenden:
Datensatz-Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-21E5-6 Versions-Permalink: https://hdl.handle.net/11858/00-001M-0000-0024-A701-2
Genre: Hochschulschrift

Dateien

einblenden: Dateien
ausblenden: Dateien
:
Maue2006.pdf (beliebiger Volltext), 2MB
 
Datei-Permalink:
-
Name:
Maue2006.pdf
Beschreibung:
-
OA-Status:
Sichtbarkeit:
Privat
MIME-Typ / Prüfsumme:
application/pdf
Technische Metadaten:
Copyright Datum:
-
Copyright Info:
-
Lizenz:
-
:
Maue2006.ps (beliebiger Volltext), 3MB
 
Datei-Permalink:
-
Name:
Maue2006.ps
Beschreibung:
-
OA-Status:
Sichtbarkeit:
Privat
MIME-Typ / Prüfsumme:
application/postscript
Technische Metadaten:
Copyright Datum:
-
Copyright Info:
-
Lizenz:
-

Externe Referenzen

einblenden:

Urheber

einblenden:
ausblenden:
 Urheber:
Maue, Jens1, Autor           
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Inhalt

einblenden:
ausblenden:
Schlagwörter: -
 Zusammenfassung: This thesis introduces a new acceleration heuristic for shortest path queries, called the PCD algorithm (\textbf{P}recomputed \textbf{C}luster \textbf{D}istances). PCD precomputes shortest path distances between the partitions of the input graph, which can be obtained by any graph partitioning method. Since the number of partitions can be varied between one and the number of nodes, the method presents an interpolation between all pairs and ordinary single source single target shortest path search. This allows a flexible trade-off between preprocessing time and space on the one hand and query time on the other, allowing significant speedups even for a sublinear amount of extra space. The method can be applied to arbitrary graphs with non-negative edge weights and does not afford a layout. Experiments on large street networks with a suitable clustering method are shown to yield average speedups of up to 114.9 for PCD as a stand-alone method. Furthermore, the algorithm's space-efficiency, simplicity, and goal-directed behaviour make PCD an alternative method to provide other acceleration heuristics with goal-direction.

Details

einblenden:
ausblenden:
Sprache(n): eng - English
 Datum: 2007-02-0120062006
 Publikationsstatus: Erschienen
 Seiten: -
 Ort, Verlag, Ausgabe: Saarbrücken : Universität des Saarlandes
 Inhaltsverzeichnis: -
 Art der Begutachtung: -
 Identifikatoren: eDoc: 314551
Anderer: Local-ID: C1256428004B93B8-FFC0D298CAFCE682C1257194003A9277-Maue2006
 Art des Abschluß: Master

Veranstaltung

einblenden:

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle

einblenden: