Engineering multilevel overlay graphs for shortest-path queries
From MaRDI portal
Publication:5406192
DOI10.1145/1412228.1412239zbMath1284.05289OpenAlexW2113276858MaRDI QIDQ5406192
Frank Schulz, Dorothea Wagner, Martin Holzer
Publication date: 1 April 2014
Published in: ACM Journal of Experimental Algorithmics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1412228.1412239
multilevelshortest pathDijkstra's algorithmpreprocessinghierarchicaloverlay graphspeed-up techniquevertex selection
Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85) Vertex degrees (05C07)
Related Items
Mvtree for hierarchical network representation based on geometric algebra subspace ⋮ Graph Bisection with Pareto Optimization ⋮ Connection Scan Algorithm ⋮ Space-efficient, fast and exact routing in time-dependent road networks ⋮ Shortest-path queries in static networks ⋮ The Shortcut Problem – Complexity and Approximation ⋮ An exact combinatorial algorithm for minimum graph bisection ⋮ Engineering Route Planning Algorithms ⋮ Energy-optimal routes for battery electric vehicles ⋮ User-Constrained Multimodal Route Planning ⋮ Customizable Contraction Hierarchies