Search-space size in contraction hierarchies

DOI10.1016/J.TCS.2016.07.003MaRDI QIDQ306264zbMATH OpenOpenAlexFDO

Authors Reinhard Bauer, Tobias Columbus, Ignaz Rutter, Dorothea Wagner

Publication date 31 August 2016

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2016.07.003

zbMATH Keywords

shortest pathscontraction hierarchiessearch space sizespeed-up techniquestheoretical analysis

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Search-space size in contraction hierarchies
• Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks
• Provable efficiency of contraction hierarchies with randomized preprocessing
• Time-dependent contraction hierarchies
• Sublinear search spaces for shortest path planning in grid and road networks

Cites work

• scientific article; zbMATH DE number 219228 (Why is no real title available?)
• scientific article; zbMATH DE number 1926659 (Why is no real title available?)
• A New Implementation of Sparse Gaussian Elimination
• Algorithmic Aspects of Vertex Elimination on Directed Graphs
• Compact oracles for reachability and approximate distances in planar digraphs
• Computing all-pairs shortest paths by leveraging low treewidth
• Generalized Nested Dissection
• Highway dimension, shortest paths, and provably efficient algorithms
• Minimal triangulations of graphs: a survey
• Minimum time-dependent travel times with contraction hierarchies
• Nested Dissection of a Regular Finite Element Mesh
• On the complexity of partitioning graphs for arc-flags
• Optimal node ranking of tree in linear time
• Polynomial-time construction of contraction hierarchies for multi-criteria objectives
• Preprocessing speed-up techniques is hard
• Provable efficiency of contraction hierarchies with randomized preprocessing
• Shortest paths in digraphs of small treewidth. I: Sequential algorithms
• The Use of Linear Graphs in Gauss Elimination
• The analysis of a nested dissection algorithm
• User-constrained multimodal route planning
• VC-dimension and shortest path algorithms

Cited in

(9)

• Space-efficient, fast and exact routing in time-dependent road networks
• Exact and approximate hierarchical hub labeling
• scientific article; zbMATH DE number 7651159 (Why is no real title available?)
• Real-time traffic assignment using engineered customizable contraction hierarchies
• Customizable hub labeling: properties and algorithms
• Improving contraction hierarchies by combining with all-pairs shortest paths problem algorithms
• Provable efficiency of contraction hierarchies with randomized preprocessing
• Search-space size in contraction hierarchies
• Fission: Practical algorithms for computing minimum balanced node separators

This page was built for publication: Search-space size in contraction hierarchies

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q306264)