Vapnik-Chervonenkis dimension and density on Johnson and Hamming graphs
From MaRDI portal
Publication:831858
DOI10.1016/j.dam.2021.09.017OpenAlexW3046383293MaRDI QIDQ831858
Bjarki Geir Benediktsson, Dugald Macpherson, Isolde Adler
Publication date: 24 March 2022
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2021.09.017
Analysis of algorithms and problem complexity (68Q25) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85) Classification theory, stability, and related concepts in model theory (03C45) Density (toughness, etc.) (05C42)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Vapnik-Chervonenkis density in some theories without the independence property. II
- Induced subgraphs of Johnson graphs
- Learnability and definability in trees and similar structures
- Quasi-optimal range searching in spaces of finite VC-dimension
- Upper bounds to the clique width of graphs
- On nowhere dense graphs
- Interpreting nowhere dense graph classes as a classical notion of model theory
- VC-dimension and Erdős-Pósa property
- Vapnik-Chervonenkis density in some theories without the independence property, I
- On the Boolean-Width of a Graph: Structure and Applications
- A theory of the learnable
- How many queries are needed to learn?
- Hitting Set for hypergraphs of low VC-dimension
- Deciding First-Order Properties of Nowhere Dense Graphs
- Neighborhood complexity and kernelization for nowhere dense classes of graphs
- Addressing Johnson Graphs, Complete Multipartite Graphs, Odd Cycles, and Random Graphs
- A Guide to NIP Theories
- Characterizing subgraphs of Hamming graphs
- Graph isomorphism in quasipolynomial time [extended abstract]
- On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
This page was built for publication: Vapnik-Chervonenkis dimension and density on Johnson and Hamming graphs
