Customizable Contraction Hierarchies
From MaRDI portal
Publication:5266613
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
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
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
