VC-dimensions for graphs (extended abstract)

DOI10.1007/3-540-60618-1_61OpenAlexW1687483116MaRDI QIDQ6122206

Berthold Ruf, Gerhard J. Woeginger, Danny Krizanc, Jorge Urrutia, Evangelos Kranakis

Publication date: 28 February 2024

Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-60618-1_61

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10) Extremal set theory (05D05)

Related Items (1)

Packing problems, dimensions and the tensor product of complete lattices

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• \(\epsilon\)-nets and simplex range queries
• 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: VC-dimensions for graphs (extended abstract)