Search-space size in contraction hierarchies

DOI10.1016/J.TCS.2016.07.003zbMATH Open1348.68173OpenAlexW2465485717MaRDI QIDQ306264FDOQ306264

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

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

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)

Cites Work

• The analysis of a nested dissection algorithm
• Generalized Nested Dissection
• Nested Dissection of a Regular Finite Element Mesh
• Minimal triangulations of graphs: a survey
• Minimum time-dependent travel times with contraction hierarchies
• Optimal node ranking of tree in linear time
• Shortest paths in digraphs of small treewidth. I: Sequential algorithms
• User-constrained multimodal route planning
• Computing all-pairs shortest paths by leveraging low treewidth
• On the complexity of partitioning graphs for arc-flags
• VC-dimension and shortest path algorithms
• The Use of Linear Graphs in Gauss Elimination
• Provable Efficiency of Contraction Hierarchies with Randomized Preprocessing
• Preprocessing speed-up techniques is hard
• A New Implementation of Sparse Gaussian Elimination
• Algorithmic Aspects of Vertex Elimination on Directed Graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Polynomial-time Construction of Contraction Hierarchies for Multi-criteria Objectives
• Title not available (Why is that?)
• Compact oracles for reachability and approximate distances in planar digraphs

Cited In (7)

• Space-efficient, fast and exact routing in time-dependent road networks
• Exact and approximate hierarchical hub labeling
• Title not available (Why is that?)
• Customizable hub labeling: properties and algorithms
• Improving contraction hierarchies by combining with all-pairs shortest paths problem algorithms
• Fission: Practical algorithms for computing minimum balanced node separators
• Real-time Traffic Assignment Using Engineered Customizable Contraction Hierarchies

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)