VC-Dimension and Shortest Path Algorithms

DOI10.1007/978-3-642-22006-7_58zbMath1334.05161MaRDI QIDQ3012843

Daniel Delling, Ittai Abraham, Renato F. Werneck, Amos Fiat, Andrew V. Goldberg

Publication date: 6 July 2011

Published in: Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-22006-7_58

Mathematics Subject Classification ID

05C38: Paths and cycles

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

Shortest-path queries in static networks, Search-space size in contraction hierarchies, Candidate Sets for Alternative Routes in Road Networks, On the Complexity of Hub Labeling (Extended Abstract), A $$(1+{\varepsilon })$$ ( 1 + ε ) -Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs, Fixed Parameter Approximations for k-Center Problems in Low Highway Dimension Graphs

Uses Software

• DIMACS

Cites Work

• Unnamed Item
• Unnamed Item
• Hitting sets when the VC-dimension is small
• Approximation algorithms for combinatorial problems
• Almost optimal set covers in finite VC-dimension
• Fast Routing in Road Networks with Transit Nodes
• Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks
• Approximate distance oracles
• Engineering Route Planning Algorithms
• Reachability and Distance Queries via 2-Hop Labels
• Distance labeling in graphs
• Algorithms – ESA 2005
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities