VC-Dimension and Shortest Path Algorithms

DOI10.1007/978-3-642-22006-7_58zbMath1334.05161OpenAlexW85521454MaRDI 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

Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (22)

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 ⋮ Search-space size in contraction hierarchies ⋮ The parameterized hardness of the \(k\)-center problem in transportation networks ⋮ On the Complexity of Hub Labeling (Extended Abstract) ⋮ Differentially private range query on shortest paths ⋮ A $(1+\varepsilon)$-Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs ⋮ On the VC-dimension of unique round-trip shortest path systems ⋮ Polynomial time approximation schemes for clustering in low highway dimension graphs ⋮ Sublinear search spaces for shortest path planning in grid and road networks ⋮ Fixed-parameter approximations for \(k\)-center problems in low highway dimension graphs ⋮ Polynomial-Time Approximation Schemes for k-center, k-median, and Capacitated Vehicle Routing in Bounded Highway Dimension ⋮ Fast approximation of betweenness centrality through sampling ⋮ Shortest-path queries in static networks ⋮ Unnamed Item ⋮ Travelling on graphs with small highway dimension ⋮ Candidate Sets for Alternative Routes in Road Networks ⋮ \(\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 ⋮ Unnamed Item ⋮ On Hop-Constrained Steiner Trees in Tree-Like Metrics ⋮ Computing Constrained Shortest-Paths at Scale

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

This page was built for publication: VC-Dimension and Shortest Path Algorithms