Engineering multilevel overlay graphs for shortest-path queries
Authors:
Open Access
- 23 February 2009
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM Journal of Experimental Algorithmics
- Vol. 13
Abstract
An overlay graph of a given graph G = ( V , E ) on a subset S ⊆ V is a graph with vertex set S and edges corresponding to shortest paths in G . In particular, we consider variations of the multilevel overlay graph used in Schulz et al. [2002] to speed up shortest-path computation. In this work, we follow up and present several vertex selection criteria, along with two general strategies of applying these criteria, to determine a subset S of a graph's vertices. The main contribution is a systematic experimental study where we investigate the impact of selection criteria and strategies on multilevel overlay graphs and the resulting speed-up achieved for shortest-path computation: Depending on selection strategy and graph type, a centrality index criterion, selection based on planar separators, and vertex degree turned out to perform best.Keywords
Funding Information
- Deutsche Forschungsgemeinschaft (WA 654/16-1)
- Seventh Framework Programme (FP6-021235-2)
This publication has 17 references indexed in Scilit:
- Engineering Highway Hierarchies2006
- Partitioning Graphs to Speed Up Dijkstra’s AlgorithmLecture Notes in Computer Science, 2005
- Engineering Planar Separator AlgorithmsLecture Notes in Computer Science, 2005
- Highway Hierarchies Hasten Exact Shortest Path Queries2005
- Combining Speed-Up Techniques for Shortest-Path Computations2004
- An efficient path computation model for hierarchically structured topographical road mapsIEEE Transactions on Knowledge and Data Engineering, 2002
- Using Multi-level Graphs for Timetable Information in Railway SystemsLecture Notes in Computer Science, 2002
- Dijkstra's algorithm on-lineACM Journal of Experimental Algorithmics, 2000
- Hierarchical encoded path views for path query processing: an optimal model and its performance evaluationIEEE Transactions on Knowledge and Data Engineering, 1998
- A note on two problems in connexion with graphsNumerische Mathematik, 1959