On the VC-dimension of unique round-trip shortest path systems

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

zbMATH Keywords

VC-dimensionshortest pathsgraph algorithmsround-trip

Mathematics Subject Classification ID

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