VC dimension VC dimension for graphs

Nicolas Bousquet

Description

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

Sujets

• Bousquet

Informations

• Publié par: pefav
• Nombre de lectures: 22
• Langue: English

Extrait

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 eachv i ∈V Constraints : for eache∈

Objective function :

, associatex i E, X x i ≥1 v i ∈e

a non negative integer.

n τ=min( X x i ) i=1

Nicolas Bousquet

VC-dimensionandErd˝os-P´operty osa pr