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
• Highway dimension, shortest paths, and provably efficient algorithms
• 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 (13)

• 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 contraction hierarchies with turn costs
• Real-time traffic assignment using engineered customizable contraction hierarchies
• Customizable hub labeling: properties and algorithms
• Title not available (Why is that?)
• 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
• Graph bisection with Pareto optimization

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)