The VC-dimension of set systems defined by graphs
type: Item
instance of: scholarly article
title: The VC-dimension of set systems defined by graphs
zbMATH Open document ID: 0879.68079
DOI: 10.1016/S0166-218X(96)00137-0
author: Evangelos Kranakis
author: D. Krizanc
author: Berthold Ruf
author: J. Urrutia
author: Gerhard J. Woeginger
published in: Discrete Applied Mathematics
publication date: 1997-12-17T00:00:00Z
full work available at URL: dam
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 1057099
zbMATH Keywords: VC-dimension
zbMATH Keywords: NP-hard problem
MaRDI profile type: Publication
cites work: The Vapnik-Chervonenkis dimension of a random graph
cites work: Learnability and the Vapnik-Chervonenkis dimension
cites work: Q3852212
cites work: Quasi-optimal range searching in spaces of finite VC-dimension
cites work: Q4198056
cites work: \(\epsilon\)-nets and simplex range queries
cites work: Q3872508
cites work: The NP-completeness column: An ongoing guide
cites work: Q5781249
cites work: On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
cites work: Node-and edge-deletion NP-complete problems
OpenAlex ID: W2040170747
Recommended article: Q5089253
Recommended article: VC dimension and a union theorem for set systems
Recommended article: Q5381136
Recommended article: The VC-dimension of graphs with respect to \(k\)-connected subgraphs
Recommended article: ON THE NUMBER OF CYCLES OF GRAPHS AND VC-DIMENSION
Recommended article: On the VC-dimension of uniform hypergraphs
Recommended article: VC-sets and generic compact domination
Recommended article: Some properties of the multiset dimension of graphs
Recommended article: VC-saturated set systems
Recommended article: VC-dimension of sets of permutations
description: scientific article; zbMATH DE number 1057099