The VC-dimension of set systems defined by graphs

DOI10.1016/S0166-218X(96)00137-0zbMath0879.68079OpenAlexW2040170747MaRDI 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

zbMATH Keywords

VC-dimensionNP-hard problem

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38)

Related Items

Diameter, Eccentricities and Distance Oracle Computations on H-Minor Free Graphs and Graphs of Bounded (Distance) Vapnik–Chervonenkis Dimension ⋮ The VC-dimension of graphs with respect to \(k\)-connected subgraphs ⋮ Boundary classes for graph problems involving non-local properties ⋮ Erdős-Hajnal conjecture for graphs with bounded VC-dimension ⋮ The cycle discrepancy of three-regular graphs ⋮ Parameterized and approximation complexity of \textsc{Partial VC Dimension} ⋮ Fast approximation of betweenness centrality through sampling ⋮ On the VC-dimension, covering and separating properties of the cycle and spanning tree hypergraphs of graphs ⋮ Bounding the trace function of a hypergraph with applications

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

This page was built for publication: The VC-dimension of set systems defined by graphs