The VC-dimension of graphs with respect to \(k\)-connected subgraphs

DOI10.1016/j.dam.2016.04.016zbMath1348.05115arXiv1302.6500OpenAlexW1806745341MaRDI QIDQ335348

Andrea Munaro

Publication date: 2 November 2016

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1302.6500

zbMATH Keywords

VC-dimensionNP-complete\(k\)-connected

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Connectivity (05C40)

Related Items (1)

Boundary classes for graph problems involving non-local properties

Cites Work

• Unnamed Item
• Unnamed Item
• Recent developments on graphs of bounded clique-width
• Matching theory
• \(\epsilon\)-nets and simplex range queries
• NP-completeness and degree restricted spanning trees
• The VC-dimension of set systems defined by graphs
• On limited nondeterminism and the complexity of the V-C dimension
• The Vapnik-Chervonenkis dimension of a random graph
• Algorithmic graph theory and perfect graphs
• Linear time solvable optimization problems on graphs of bounded clique-width
• Upper bounds to the clique width of graphs
• Split permutation graphs
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Parallel Complexity of the Connected Subgraph Problem
• Computational Complexity
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities

This page was built for publication: The VC-dimension of graphs with respect to \(k\)-connected subgraphs