Customizable contraction hierarchies

DOI10.1145/2886843zbMATH Open1365.68353DBLPjournals/jea/DibbeltSW16arXiv1402.0402OpenAlexW1904636577WikidataQ56609663 ScholiaQ56609663MaRDI QIDQ5266613FDOQ5266613

Authors: Julian Dibbelt, Ben Strasser, Dorothea Wagner 

Publication date: 16 June 2017

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

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.

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

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

zbMATH Keywords

contractiondistance oracleroute planningspeedup technique

Mathematics Subject Classification ID

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

Cites Work

• A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs
• A note on two problems in connexion with graphs
• The analysis of a nested dissection algorithm
• The Evolution of the Minimum Degree Ordering Algorithm
• Generalized Nested Dissection
• Nested Dissection of a Regular Finite Element Mesh
• Hierarchical Hub Labelings for Shortest Paths
• Incidence matrices and interval graphs
• Title not available (Why is that?)
• Computing the Minimum Fill-In is NP-Complete
• Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval Graphs
• Shortest paths in digraphs of small treewidth. I: Sequential algorithms
• Computing all-pairs shortest paths by leveraging low treewidth
• Preprocessing speed-up techniques is hard
• Title not available (Why is that?)
• Treewidth computations. I: Upper bounds
• Title not available (Why is that?)
• Alternative routes in road networks
• Treewidth: Structure and Algorithms
• Exact Combinatorial Branch-and-Bound for Graph Bisection
• The Shortcut Problem - Complexity and Algorithms
• Search-Space Size in Contraction Hierarchies
• Title not available (Why is that?)
• Engineering multilevel overlay graphs for shortest-path queries
• Robust Distance Queries on Massive Networks
• Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks
• Evolution and Evaluation of the Penalty Method for Alternative Graphs
• Dijkstra's algorithm on-line
• Fast detour computation for ride sharing
• Graph Bisection with Pareto-Optimization
• Engineering highway hierarchies
• Title not available (Why is that?)

Cited In (12)

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

Uses Software

• DIMACS
• ComputeTW

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)