Sample Compression Schemes for Balls in Graphs
From MaRDI portal
Publication:6069434
DOI10.1137/22m1527817arXiv2206.13254MaRDI QIDQ6069434
Fionn Mc Inerney, Yann Vaxès, Sébastien Ratel, Jérémie Chalopin, Victor Chepoi
Publication date: 14 November 2023
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2206.13254
Computational learning theory (68Q32) Graph theory (including graph drawing) in computer science (68R10) Distance in graphs (05C12)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On embeddings of CAT(0) cube complexes into products of trees via colouring their hyperplanes
- Shortest path problem in rectangular complexes of global nonpositive curvature
- Finding cactus roots in polynomial time
- Covering planar graphs with a fixed number of balls
- Ramified rectilinear polygons: coordinatization by dendrons
- Trees, tight extensions of metric spaces, and the cohomological dimension of certain groups: A note on combinatorial properties of metric spaces
- Some special Vapnik-Chervonenkis classes
- Balls in \(\mathbb{R}^k\) do not cut all subsets of \(k+2\) points
- Combinatorial variability of Vapnik-Chervonenkis classes with applications to sample compression schemes
- Unlabeled sample compression schemes and corner peelings for ample and maximum classes
- Distance and routing labeling schemes for cube-free median graphs
- Unlabeled compression schemes exceeding the VC-dimension
- VC-dimension and Erdős-Pósa property
- Six theorems about injective metric spaces
- Kernelization and approximation of distance-\(r\) independent sets on nowhere dense graphs
- Labeled Compression Schemes for Extremal Classes
- INJECTIVE HULLS OF CERTAIN DISCRETE METRIC SPACES AND GROUPS
- Sample Compression Schemes for VC Classes
- Uniform Central Limit Theorems
- Bounding the Order of a Graph Using Its Diameter and Metric Dimension: A Study Through Tree Decompositions and VC Dimension
- Diameter, Eccentricities and Distance Oracle Computations on H-Minor Free Graphs and Graphs of Bounded (Distance) Vapnik–Chervonenkis Dimension
- On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
