Engineering multilevel overlay graphs for shortest-path queries

DOI10.1145/1412228.1412239MaRDI QIDQ5406192zbMATH OpenOpenAlexFDO

Authors Martin Holzer, Frank Schulz, Dorothea Wagner

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

zbMATH Keywords

Dijkstra's algorithmhierarchicalmultileveloverlay graphpreprocessingshortest pathspeed-up techniquevertex selection

Mathematics Subject Classification ID

Vertex degrees (05C07) Distance in graphs (05C12) Extremal problems in graph theory (05C35) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Engineering multi-level overlay graphs for shortest-path queries
• Dynamic multi-level overlay graphs for shortest paths
• High-performance multi-level routing
• Shortest-path queries in static networks
• scientific article; zbMATH DE number 2081016

Cited in

(13)

• Mvtree for hierarchical network representation based on geometric algebra subspace
• Energy-optimal routes for battery electric vehicles
• User-constrained multimodal route planning
• The Shortcut Problem – Complexity and Approximation
• Engineering Route Planning Algorithms
• Graph bisection with Pareto optimization
• Connection Scan Algorithm
• Shortest-path queries in static networks
• Engineering multi-level overlay graphs for shortest-path queries
• Customizable contraction hierarchies
• Space-efficient, fast and exact routing in time-dependent road networks
• An exact combinatorial algorithm for minimum graph bisection
• Dynamic multi-level overlay graphs for shortest paths

This page was built for publication: Engineering multilevel overlay graphs for shortest-path queries

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5406192)