The VC-dimension of set systems defined by graphs
From MaRDI portal
Publication:1364472
DOI10.1016/S0166-218X(96)00137-0zbMath0879.68079MaRDI QIDQ1364472
Jorge Urrutia, Evangelos Kranakis, Danny Krizanc, Berthold Ruf, Gerhard J. Woeginger
Publication date: 17 December 1997
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: http://www.elsevier.com/locate/dam
Related Items
The VC-dimension of graphs with respect to \(k\)-connected subgraphs, The cycle discrepancy of three-regular graphs, Parameterized and approximation complexity of \textsc{Partial VC Dimension}, Fast approximation of betweenness centrality through sampling, Boundary classes for graph problems involving non-local properties, Erdős-Hajnal conjecture for graphs with bounded VC-dimension
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- \(\epsilon\)-nets and simplex range queries
- Quasi-optimal range searching in spaces of finite VC-dimension
- The Vapnik-Chervonenkis dimension of a random graph
- Learnability and the Vapnik-Chervonenkis dimension
- Node-and edge-deletion NP-complete problems
- On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
- The NP-completeness column: An ongoing guide