The VC-dimension of graphs with respect to \(k\)-connected subgraphs
type: Item
instance of: scholarly article
title: The VC-dimension of graphs with respect to \(k\)-connected subgraphs
zbMATH Open document ID: 1348.05115
author: Andrea Munaro
published in: Discrete Applied Mathematics
publication date: 2016-11-02T00:00:00Z
full work available at URL: https://arxiv.org/abs/1302.6500
Mathematics Subject Classification ID: 05C40
Mathematics Subject Classification ID: 68Q17
zbMATH DE Number: 6646870
zbMATH Keywords: VC-dimension
zbMATH Keywords: \(k\)-connected
zbMATH Keywords: NP-complete
MaRDI profile type: Publication
OpenAlex ID: W1806745341
arXiv ID: 1302.6500
cites work: Q3888545
cites work: The Vapnik-Chervonenkis dimension of a random graph
cites work: Computational Complexity
cites work: The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
cites work: Linear time solvable optimization problems on graphs of bounded clique-width
cites work: Upper bounds to the clique width of graphs
cites work: NP-completeness and degree restricted spanning trees
cites work: Q4198056
cites work: Algorithmic graph theory and perfect graphs
cites work: \(\epsilon\)-nets and simplex range queries
cites work: Recent developments on graphs of bounded clique-width
cites work: Parallel Complexity of the Connected Subgraph Problem
cites work: Split permutation graphs
cites work: The VC-dimension of set systems defined by graphs
cites work: Matching theory
cites work: On limited nondeterminism and the complexity of the V-C dimension
cites work: On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
DOI: 10.1016/J.DAM.2016.04.016
description: scientific article