Max-Planck-Institut für Informatik
max planck institut
informatik
mpii logo Minerva of the Max Planck Society
 

MPI-INF D1 Publications :: Thesis :: Maue, Jens


MPI-INF D1 Publications
Show all entries of:this year (2019)last year (2018)two years ago (2017)Open in Notes
Action:login to update

Thesis - Master's thesis | @MastersThesis | Masterarbeit


Author
Author(s)*:Maue, Jens
BibTeX citekey*:Maue2006
Language:English

Title, School
Title*:A Goal-Directed Shortest Path Algorithm Using Precomputed Cluster Distances
School:Universität des Saarlandes
Type of Thesis*:Master's thesis
Month:June
Year:2006


Note, Abstract, Copyright
LaTeX Abstract: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.

Keywords:Shortest Paths, Preprocessing Heuristics, Graph Algorithms
Download Access Level:Public
Download File(s):View attachments here:

Referees, Status, Dates
1. Referee:Prof. Dr. Kurt Mehlhorn
2. Referee:Prof. Dr. Peter Sanders
Status:Completed
Date Kolloquium:- - -

Correlation
MPG Unit:Max-Planck-Institut für Informatik
MPG Subunit:Algorithms and Complexity Group
Appearance:MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort


BibTeX Entry:
@MASTERSTHESIS{Maue2006,
AUTHOR = {Maue, Jens},
TITLE = {A Goal-Directed Shortest Path Algorithm Using Precomputed Cluster Distances},
SCHOOL = {Universit{\"a}t des Saarlandes},
YEAR = {2006},
TYPE = {Master's thesis}
MONTH = {June},
}





Entry last modified by Christine Kiesel, 02/01/2007
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Jens Maue
Created
06/21/2006 12:39:45 PM
Revisions
5.
4.
3.
2.
1.
Editor(s)
Christine Kiesel
Jens Maue
Jens Maue
Jens Maue
Jens Maue
Edit Dates
01.02.2007 08:33:08
06/26/2006 12:06:33 PM
06/22/2006 12:37:08 PM
06/21/2006 12:49:15 PM
06/21/2006 12:48:25 PM