KIT | KIT-Bibliothek | Impressum

Geometric shortest path containers [online]

Wagner, Dorothea; Wilhalm, Thomas; Zaroliagis, Christos

Abstract:

In this paper, we consider Dijkstra's algorithm for the
single source single target shortest path problem in large
sparse graphs.
The goal is to reduce the response time for on-line queries by
using precomputed information.
Due to the size of the graph, preprocessing space requirements
can be only linear in the number of nodes.
We assume that a layout of the graph is given.
In the preprocessing, we determine from this layout a geometric
object for each edge containing all nodes that can be reached by
a shortest path starting with that edge.
Based on these geometric objects, the search space for on-line
computation can be reduced significantly.
Shortest path queries can then be answered by Dijkstra's
algorithm restricted to edges where the corresponding geometric
object contains the target.

We present an extensive experimental study comparing the impact
of different types of objects.
The test data we use are real-world traffic networks, the
typical field of application for this scenario.
Furthermore, we present new algorithms as well as an empirical
study for the dynamic case of this problem, where edge weights
are subject to chang ... mehr


Zugehörige Institution(en) am KIT Institut für Logik, Komplexität und Deduktionssysteme (ILKD)
Publikationstyp Buch
Jahr 2004
Sprache Englisch
Identifikator URN: urn:nbn:de:swb:90-AAA8420041
KITopen ID: 842004
Erscheinungsvermerk Karlsruhe 2004. (Interner Bericht. Fakultät für Informatik, Universität Karlsruhe. 2004,5.)
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft KITopen Landing Page