Dynamic multi-level overlay graphs for shortest paths
Mathematics in Computer Science, 2008•Springer
Multi-level overlay graphs represent a speed-up technique for shortest paths computation
which is based on a hierarchical decomposition of a weighted directed graph G. They have
been shown to be experimentally efficient, especially when applied to timetable information.
However, no theoretical result on the cost of constructing, maintaining and querying multi-
level overlay graphs in a dynamic environment is known. In this paper, we show theoretical
properties of multi-level overlay graphs that lead us to the definition of a new data structure …
which is based on a hierarchical decomposition of a weighted directed graph G. They have
been shown to be experimentally efficient, especially when applied to timetable information.
However, no theoretical result on the cost of constructing, maintaining and querying multi-
level overlay graphs in a dynamic environment is known. In this paper, we show theoretical
properties of multi-level overlay graphs that lead us to the definition of a new data structure …
Abstract
Multi-level overlay graphs represent a speed-up technique for shortest paths computation which is based on a hierarchical decomposition of a weighted directed graph G. They have been shown to be experimentally efficient, especially when applied to timetable information. However, no theoretical result on the cost of constructing, maintaining and querying multi-level overlay graphs in a dynamic environment is known.
In this paper, we show theoretical properties of multi-level overlay graphs that lead us to the definition of a new data structure for the computation and the maintenance of an overlay graph of G while weight decrease or weight increase operations are performed on G. Our solution is theoretically faster than the recomputation from scratch and allows queries that can be performed more efficiently than running Dijkstra’s shortest paths algorithm on G.
Springer
Showing the best result for this search. See all results