English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
Add to Basket
 Local TagsRelease HistoryDetailsSummary
  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

 

show all hide all

Basic

show hide
Item Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-21E5-6 Version Permalink: https://hdl.handle.net/11858/00-001M-0000-0024-A701-2
Genre: Thesis

Files

show Files
hide Files
:
Maue2006.pdf (Any fulltext), 2MB
 
File Permalink:
-
Name:
Maue2006.pdf
Description:
-
OA-Status:
Visibility:
Private
MIME-Type / Checksum:
application/pdf
Technical Metadata:
Copyright Date:
-
Copyright Info:
-
License:
-
:
Maue2006.ps (Any fulltext), 3MB
 
File Permalink:
-
Name:
Maue2006.ps
Description:
-
OA-Status:
Visibility:
Private
MIME-Type / Checksum:
application/postscript
Technical Metadata:
Copyright Date:
-
Copyright Info:
-
License:
-

Locators

show

Creators

show
hide
 Creators:
Maue, Jens1, Author           
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Content

show
hide
Free keywords: -
 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.

Details

show
hide
Language(s): eng - English
 Dates: 2007-02-0120062006
 Publication Status: Issued
 Pages: -
 Publishing info: Saarbrücken : Universität des Saarlandes
 Table of Contents: -
 Rev. Type: -
 Identifiers: eDoc: 314551
Other: Local-ID: C1256428004B93B8-FFC0D298CAFCE682C1257194003A9277-Maue2006
 Degree: Master

Event

show

Legal Case

show

Project information

show

Source

show