Customizable Contraction Hierarchies

DOI10.1145/2886843zbMath1365.68353arXiv1402.0402OpenAlexW1904636577WikidataQ56609663 ScholiaQ56609663MaRDI QIDQ5266613

Ben Strasser, Julian Dibbelt, Dorothea Wagner

Publication date: 16 June 2017

Published in: ACM Journal of Experimental Algorithmics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1402.0402

zbMATH Keywords

contractionroute planningdistance oraclespeedup technique

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10) Deterministic network models in operations research (90B10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Graph Bisection with Pareto Optimization, Unnamed Item, Customizable hub labeling: properties and algorithms, Fission: Practical algorithms for computing minimum balanced node separators, Unnamed Item, Space-efficient, fast and exact routing in time-dependent road networks, Sublinear search spaces for shortest path planning in grid and road networks, PACE Solver Description: Tree Depth with FlowCutter, Evaluation of a Flow-Based Hypergraph Bipartitioning Algorithm, Energy-optimal routes for battery electric vehicles, An Experimental Study of the Treewidth of Real-World Graph Data, Real-time Traffic Assignment Using Engineered Customizable Contraction Hierarchies

Uses Software

• DIMACS
• ComputeTW

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on two problems in connexion with graphs
• Treewidth computations. I: Upper bounds
• The analysis of a nested dissection algorithm
• Shortest paths in digraphs of small treewidth. I: Sequential algorithms
• Incidence matrices and interval graphs
• Computing All-Pairs Shortest Paths by Leveraging Low Treewidth
• Hierarchical Hub Labelings for Shortest Paths
• Fast Detour Computation for Ride Sharing
• Robust Distance Queries on Massive Networks
• The Shortcut Problem - Complexity and Algorithms
• Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks
• Preprocessing Speed-Up Techniques Is Hard
• The Evolution of the Minimum Degree Ordering Algorithm
• Generalized Nested Dissection
• Computing the Minimum Fill-In is NP-Complete
• A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs
• Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval Graphs
• Alternative routes in road networks
• Graph Bisection with Pareto-Optimization
• Exact Combinatorial Branch-and-Bound for Graph Bisection
• Search-Space Size in Contraction Hierarchies
• Evolution and Evaluation of the Penalty Method for Alternative Graphs
• Engineering multilevel overlay graphs for shortest-path queries
• Engineering highway hierarchies
• Treewidth: Structure and Algorithms
• Dijkstra's algorithm on-line
• Nested Dissection of a Regular Finite Element Mesh