VC-Dimension and Shortest Path Algorithms

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

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

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

Unnamed Item, Computing Constrained Shortest-Paths at Scale, Polynomial-Time Approximation Schemes for k-center, k-median, and Capacitated Vehicle Routing in Bounded Highway Dimension, Shortest-path queries in static networks, The Parameterized Hardness of the k-Center Problem in Transportation Networks, A $(1+\varepsilon)$-Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs, Unnamed Item, Travelling on graphs with small highway dimension, On Hop-Constrained Steiner Trees in Tree-Like Metrics, Search-space size in contraction hierarchies, Fixed-parameter approximations for \(k\)-center problems in low highway dimension graphs, On the VC-dimension of unique round-trip shortest path systems, Fast approximation of betweenness centrality through sampling, \(\mathsf{W[1}\)-hardness of the \(k\)-center problem parameterized by the skeleton dimension], The parameterized hardness of the \(k\)-center problem in transportation networks, Polynomial time approximation schemes for clustering in low highway dimension graphs, Sublinear search spaces for shortest path planning in grid and road networks, 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