//img.uscri.be/pth/c088572213a278d51e61783dcca05d94148e301f
Cet ouvrage fait partie de la bibliothèque YouScribe
Obtenez un accès à la bibliothèque pour le lire en ligne
En savoir plus

VC dimension VC dimension for graphs

De
55 pages
VC-dimension VC-dimension for graphs Conclusion VC-dimension and Erdo˝s-Posa property Nicolas Bousquet LIRMM, University Montpellier II Nicolas Bousquet VC-dimension and Erdo˝s-Posa property

  • dual vc-dimension

  • university montpellier

  • erdo˝s-posa property

  • linear programing

  • vc-dimension applications


Voir plus Voir moins
VC-dimension VC-dimension for graphs Conclusion
VC-dimension
and
Nicolas
LIRMM,
Erdo˝s-Po´sa
Bousquet
University
Nicolas Bousquet
Montpellier
property
II
VC-dimensionandErd˝os-Po´saproperty
1
2
3
VC-dimension VC-dimension for graphs Conclusion
VC-dimension Packing and transversality VC-dimension Applications
Packing and transversality VC-dimension Applications
VC-dimension for graphs Dual VC-dimension VC-dimension of graphs Classes of graphs of bounded VC-dimension Erd˝os-Po´saproperty
Conclusion
Nicolas Bousquet
VC-dimensionandErd˝os-Po´saproperty
VC-dimension VC-dimension for graphs Conclusion
Packing and transversality VC-dimension Applications
Definition Ahypergraphis a pair (V,E) whereVis a set of hyperedges (subsets of vertices).
Nicolas Bousquet
a
set
of
vertices
VC-dimensionandErd˝os-Po´saproperty
and
E
is
VC-dimension VC-dimension for graphs Conclusion
Packing and transversality VC-dimension Applications
Definition Thetransversalityτof a hypergraph is the vertices which intersect all the hyperedges.
Nicolas Bousquet
minimum
number
VC-dimensionandErd˝os-Po´saproperty
of
VC-dimension VC-dimension for graphs Conclusion
Packing and transversality VC-dimension Applications
Definition Thetransversalityτof a hypergraph is the minimum number of vertices which intersect all the hyperedges.
Linear Programing Variables : for eachviV Constraints : for eache
Objective function :
, associatexi E, Xxi1 vie
a non negative integer.
n τ=min(Xxi) i=1
Nicolas Bousquet
VC-dimensionandErd˝os-P´operty osa pr