On the VC-dimension of unique round-trip shortest path systems
From MaRDI portal
Publication:1730015
DOI10.1016/j.ipl.2019.01.001zbMath1451.05233OpenAlexW2909756033WikidataQ91332565 ScholiaQ91332565MaRDI QIDQ1730015
Kam-Yiu Lam, Jinbo Bi, Chun Jiang Zhu, Joseph Kee-Yin Ng
Publication date: 11 March 2019
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: http://europepmc.org/articles/pmc6860909
Combinatorial optimization (90C27) Paths and cycles (05C38) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Hitting sets when the VC-dimension is small
- \(\epsilon\)-nets and simplex range queries
- On sparse spanners of weighted graphs
- Almost optimal set covers in finite VC-dimension
- Deterministic improved round-trip spanners
- Source-wise round-trip spanners
- VC-Dimension and 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
- Beyond Highway Dimension: Small Distance Labels Using Tree Skeletons
- Roundtrip spanners and roundtrip routing in directed graphs
- Polynomial-Time Approximation Schemes for k-center, k-median, and Capacitated Vehicle Routing in Bounded Highway Dimension
- Algorithms for polytope covering and approximation
- Compact roundtrip routing in directed networks (extended abstract)
- A $(1+\varepsilon)$-Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs
- On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
This page was built for publication: On the VC-dimension of unique round-trip shortest path systems
