### Engineering multilevel overlay graphs for shortest-path queriesEngineering multilevel overlay graphs for shortest-path queries

Access Restriction
Subscribed

 Author Holzer, Martin ♦ Schulz, Frank ♦ Wagner, Dorothea Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2009 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Computer programming, programs & data Subject Keyword Dijkstra's algorithm ♦ Hierarchical ♦ Multilevel ♦ Overlay graph ♦ Preprocessing ♦ Shortest path ♦ Speed-up technique ♦ Vertex selection Abstract An overlay graph of a given graph $\textit{G}$ = $(\textit{V},$ $\textit{E})$ on a subset $\textit{S}$ ⊆ $\textit{V}$ is a graph with vertex set $\textit{S}$ and edges corresponding to shortest paths in $\textit{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 $\textit{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. ISSN 10846654 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2009-02-01 Publisher Place New York e-ISSN 10846654 Journal Journal of Experimental Algorithmics (JEA) Volume Number 13 Page Count 22 Starting Page 2.5 Ending Page 2.26

#### Open content in new tab

Source: ACM Digital Library