Customizable contraction hierarchies
From MaRDI portal
Abstract: We consider the problem of quickly computing shortest paths in weighted graphs given auxiliary data derived in an expensive preprocessing phase. By adding a fast weight-customization phase, we extend Contraction Hierarchies by Geisberger et al to support the three-phase workflow introduced by Delling et al. Our Customizable Contraction Hierarchies use nested dissection orders as suggested by Bauer et al. We provide an in-depth experimental analysis on large road and game maps that clearly shows that Customizable Contraction Hierarchies are a very practicable solution in scenarios where edge weights often change.
Recommendations
- Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks
- Time-dependent contraction hierarchies
- Engineering Highway Hierarchies
- Provable efficiency of contraction hierarchies with randomized preprocessing
- Real-time traffic assignment using engineered customizable contraction hierarchies
Cites work
- A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs
- A note on two problems in connexion with graphs
- Alternative routes in road networks
- Computing all-pairs shortest paths by leveraging low treewidth
- Computing the Minimum Fill-In is NP-Complete
- Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks
- Dijkstra's algorithm on-line
- Engineering highway hierarchies
- Engineering multilevel overlay graphs for shortest-path queries
- Evolution and evaluation of the penalty method for alternative graphs
- Exact combinatorial branch-and-bound for graph bisection
- Fast detour computation for ride sharing
- Generalized Nested Dissection
- Graph bisection with Pareto-optimization
- Hierarchical hub labelings for shortest paths
- Highway dimension, shortest paths, and provably efficient algorithms
- scientific article; zbMATH DE number 5610761 (Why is no real title available?)
- scientific article; zbMATH DE number 3631853 (Why is no real title available?)
- scientific article; zbMATH DE number 566078 (Why is no real title available?)
- scientific article; zbMATH DE number 1956212 (Why is no real title available?)
- Incidence matrices and interval graphs
- Nested Dissection of a Regular Finite Element Mesh
- Preprocessing speed-up techniques is hard
- Robust distance queries on massive networks
- Search-space size in contraction hierarchies
- Shortest paths in digraphs of small treewidth. I: Sequential algorithms
- The analysis of a nested dissection algorithm
- The Evolution of the Minimum Degree Ordering Algorithm
- The shortcut problem - complexity and algorithms
- Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval Graphs
- Treewidth computations. I: Upper bounds
- Treewidth: Structure and Algorithms
Cited in
(15)- Sublinear search spaces for shortest path planning in grid and road networks
- Energy-optimal routes for battery electric vehicles
- Graph bisection with Pareto optimization
- Real-time traffic assignment using engineered customizable contraction hierarchies
- Evaluation of a Flow-Based Hypergraph Bipartitioning Algorithm
- An Experimental Study of the Treewidth of Real-World Graph Data
- Engineering graph-based models for dynamic timetable information systems
- scientific article; zbMATH DE number 7651159 (Why is no real title available?)
- Space-efficient, fast and exact routing in time-dependent road networks
- PACE Solver Description: Tree Depth with FlowCutter
- Customizable hub labeling: properties and algorithms
- Fission: Practical algorithms for computing minimum balanced node separators
- Customizable contraction hierarchies with turn costs
- Adaptive forecast-driven repositioning for dynamic ride-sharing
- Combining predicted and live traffic with time-dependent A^* potentials
This page was built for publication: Customizable contraction hierarchies
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5266613)
