Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks

DOI10.1007/978-3-540-68552-4_24zbMath1430.68208MaRDI QIDQ3506418

Robert Geisberger, Daniel Delling, Dominik Schultes, Peter Sanders

Publication date: 13 June 2008

Published in: Experimental Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-68552-4_24

Mathematics Subject Classification ID

68W40: Analysis of algorithms

68R10: Graph theory (including graph drawing) in computer science

90B20: Traffic problems in operations research

Related Items

KADABRA is an ADaptive Algorithm for Betweenness via Random Approximation, Unnamed Item, Unnamed Item, Unnamed Item, Computing Constrained Shortest-Paths at Scale, The compressed differential heuristic, Shortest-path queries in static networks, ReHub, Customizable Contraction Hierarchies, Unnamed Item, Regarding Goal Bounding and Jump Point Search, Solving the Watchman Route Problem with Heuristic Search, Conflict-tolerant and conflict-free multi-agent meeting, PACE Solver Description: Tree Depth with FlowCutter, Generating constrained length personalized bicycle tours, Fast optimal and bounded suboptimal Euclidean pathfinding, Finding the shortest path with vertex constraint over large graphs, Speeding up Martins' algorithm for multiple objective shortest path problems, User-Constrained Multimodal Route Planning, VC-Dimension and Shortest Path Algorithms, Engineering Route Planning Algorithms, Car or Public Transport—Two Worlds

Cites Work

• Fast Routing in Road Networks with Transit Nodes
• SHARC: Fast and Robust Unidirectional Routing
• Better Approximation of Betweenness Centrality
• Goal Directed Shortest Path Queries Using Precomputed Cluster Distances
• Engineering Highway Hierarchies
• Algorithms – ESA 2005
• Experimental and Efficient Algorithms
• Unnamed Item