Cet ouvrage fait partie de la bibliothèque YouScribe
Obtenez un accès à la bibliothèque pour le lire en ligne
En savoir plus

Augmentation de l'arête connexité d'un hypergraphe sous contraintes de partition

De
59 pages
Augmentation de l'arête-connexité d'un hypergraphe Roland Grappe1 Travail commun avec A. Bernáth2 et Z. Szigeti1 1 Laboratoire G-SCOP 2 Egerváry Research Group JGA 6 Novembre 2009 Roland Grappe (G-SCOP, Grenoble) Augmentation d'un hypergraphe JGA 6 Novembre 2009 1 / 27

  • arête-connexité

  • arête

  • hypergraphe jga


Voir plus Voir moins
RolanCS-GG,POarGd(eppgmAutaennoree)blgraryhepdnuitnobre2ovemGA6NpheJ
JGA 6 Novembre 2009
1Laboratoire G-SCOP 2Egerváry Research Group
Roland Grappe1 Travail commun avec A. Bernáth2et Z. Szigeti1
Augmentation de l’arête-connexité d’un hypergraphe
72/1900
4
. . . sous contraintes de partition
1
Augmentation de l’arête-connexité d’un graphe
Plan
Augmentation de l’arête-connexité d’un hypergraphe
3
2
. . . sous contraintes de partition
ndGrappeRolaundioatntmeug)AelbonerG,POCS-G(2/272009mbreNoveGJ6Apaehrerghnpy
nebo,PrGguemelA)Grapland-SCOpe(GoRre20093/27
Problèmes
Augmentation de l’arête-connexité d’unhypergraphe
Augmentation de l’arête-connexité d’un graphe sousconstraintes de partition
Augmentation de l’arête-connexité d’un graphe
Augmentation de l’arête-connexité d’unhypergraphe sousconstraintes de partition
pargGJehoN6Abmevatntndionhueryp
-SCOpe(GGraplandguemelA)nebo,PrGerypnhundioatntbmevoN6AGJehpargoRer0290/472
Plan
3
Augmentation de l’arête-connexité d’un hypergraphe
. . . sous contraintes de partition
4
1
Augmentation de l’arête-connexité d’un graphe
2
. . . sous contraintes de partition
tnemguA)elbonerGP,CO-S(GpeapGrndbmeroNevGJ6ApaehergrnhypnduatiooRal900272/5
kchaînes arête-disjointes entreuetv,uv
G= (VE)estk-arête-connexe:
Définitions : arête-connexité et coupes graphesnonorientés,pas decoûts
u
v
Un pour Un
Permettre à tous d'accéder à la lecture
Pour chaque accès à la bibliothèque, YouScribe donne un accès à une personne dans le besoin