VC-dimension and shortest path algorithms
From MaRDI portal
Recommendations
- On the VC-dimension of unique round-trip shortest path systems
- Highway dimension and provably efficient shortest path algorithms
- A Range Space with Constant VC Dimension for All-pairs Shortest Paths in Graphs
- The VC-dimension of set systems defined by graphs
- Highway dimension, shortest paths, and provably efficient algorithms
Cites work
- Algorithms – ESA 2005
- Almost optimal set covers in finite VC-dimension
- Approximate distance oracles
- Approximation algorithms for combinatorial problems
- Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks
- Distance labeling in graphs
- Engineering Route Planning Algorithms
- Fast Routing in Road Networks with Transit Nodes
- Highway dimension, shortest paths, and provably efficient algorithms
- Hitting sets when the VC-dimension is small
- On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
- Reach for A^*: shortest path algorithms with preprocessing
- Reachability and Distance Queries via 2-Hop Labels
Cited in
(29)- 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
- VC-dimensions of short Presburger formulas
- Candidate sets for alternative routes in road networks
- On the complexity of hub labeling (extended abstract)
- Search-space size in contraction hierarchies
- Highway dimension and provably efficient shortest path algorithms
- 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
- Note on the Complexity of the Shortest Path Models for Column Generation in VRPTW
- Polynomial-Time Approximation Schemes for k-center, k-median, and Capacitated Vehicle Routing in Bounded Highway Dimension
- Computing constrained shortest-paths at scale
- Exploiting hopsets: improved distance oracles for graphs of constant highway dimension and beyond
- The parameterized hardness of the \(k\)-center problem in transportation networks
- Shortest-path queries in static networks
- A (1+\varepsilon)-Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs
- Exact distance oracles for planar graphs
- On Hop-Constrained Steiner Trees in Tree-Like Metrics
- Travelling on graphs with small highway dimension
- A Range Space with Constant VC Dimension for All-pairs Shortest Paths in Graphs
- VC-dimensions for graphs (extended abstract)
- Differentially private range query on shortest paths
- Fixed-parameter approximations for \(k\)-center problems in low highway dimension graphs
- On sparse hitting sets: from fair vertex cover to highway dimension
- Parameterized upper bounds for path-consistent hub labeling
This page was built for publication: VC-dimension and shortest path algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3012843)
