Ordonnancement chromatique - =1=polyèdres, complexité et …vjost/Soutenance_Jost.pdf · 2007. 3. 13. · Ordonnancement chromatique p oly èdres, complexité et classi cation Vincent

Ordonnanement hromatiquepolyèdres, omplexité et lassi�ationVinent JOSTEnadrement : Nadia BRAUNER, András SEBUniversité Joseph Fourier, Grenoble ILaboratoire Leibniz-IMAG 1

Ordonnanement par baths

I1 b b I2 b bI3 b bI4 b bI5 b bI6 b bI7 b bI8 b b01234

5678 Tolérane de températureTemps minimumde uisson

500 1000 1500 2000 C 3

Ordonnanement par baths◮ Représentation par un graphe pondéréI1 b bI2 b bI3 b bI4 b bI5 b bI6 b bI7 b bI8 b b0246

8Température

Tempsuisson (I1, 2) (I2, 4)(I3, 5)(I4, 8) (I5, 7)(I6, 6)(I7, 2) (I8, 4)bbbb bbbb

bbbb

bbbbb

b

b

b

b b

b b

b bb

b

b

bb

b

b

bb

bb

b

4

Ordonnanement par baths : partition en liques◮ {Baths réalisables} = {Cliques du graphe d'intervalles}I1 b bI2 b bI3 b bI4 b bI5 b bI6 b bI7 b bI8 b b0246

8Température


bbbb

bbbbb

b

b

b

b b

b b

b bb

b

b

bb

b

b

bb

bb

b

bb

bb

bb 4

Ordonnanement par baths parallèles◮ Temps d'opération d'un bath := maximum des tempsI1 b bI2 b bI3 b bI4 b bI5 b bI6 b bI7 b bI8 b b6 Température


bbbb

bbbbb

b

b

b

b b

b b

b bb

b

b

bb

b

b

bb

bb

b

bb

bb

bb 4

Ordonnanement par baths : diagramme de Gantt◮ 3 représentations d'une solutionI1 b bI2 b bI3 b bI4 b bI5 b bI6 b bI7 b bI8 b b826 Température


bbbb

bbbbb

b

b

b

b b

b b

b bb

b

b

bb

b

b

bb

bb

b

bb

bb

bb

bb

bb

bb

bb

bb

I2 I3 I4 I5 I1 I6 I7 I88 10 16 Ci 4

Ordonnanement par baths : taille du four bornée◮ Chaque bath ontient au plus b tâhes (exemple b = 3)I1 b bI2 b bI3 b bI4 b bI5 b bI6 b bI7 b bI8 b b856 Température


bbbb

bbbbb

b

b

b

b b

b b

b bb

b

b

bb

b

b

bb

bb

b

bb

bb

bb

bb

bb

bb

bb

bb

I2 I4 I5 I1 I3 I6 I7 I88 13 19 Ci 4

Menu du jour◮ I) Partition en liques : théorie lassique

5

Menu du jour◮ I) Partition en liques : théorie lassique◮ II) Extension de pré-partition en liques [PrExt℄

5

Menu du jour◮ I) Partition en liques : théorie lassique◮ II) Extension de pré-partition en liques [PrExt℄◮ III) Partition en liques bornées [PCliqB℄

5

Menu du jour◮ I) Partition en liques : théorie lassique◮ II) Extension de pré-partition en liques [PrExt℄◮ III) Partition en liques bornées [PCliqB℄◮ IV) Partition de oût minimum [PCliqW℄ 5

I) Partition en liques : théorie lassique6

Dé�nitions utiles◮ Le graphe omplémentaire

b

b

b bb

bb bb

bb

b bb b

bb b

Gb

bb

bb

bb

b

G7

Dé�nitions utiles◮ Le graphe omplémentaire◮ Sous-graphe induit

b

b

b bb

bb bb

bb

b bb b

bb b

G7

Dé�nitions utiles◮ Le graphe omplémentaire◮ Sous-graphe induit

b

b

b bb

bb bb

bb

b bb b

bb bbbbb

bb

bb

(G ,U)7

Dé�nitions utiles◮ Le graphe omplémentaire◮ Sous-graphe induit par U ⊆ V

b

b

b bb

bb bb

bb

b bb b

bb bbbbb

bb

bb

(G ,U)b

bb bb

b

bb b

bb bb bb

b

b

b

G[U]7

Dé�nitions utiles◮ Le graphe omplémentaire◮ Sous-graphe induit par U ⊆ V◮ Clique et stable

b

b

b bb

bb bb

bb

b bb b

bb b b

bb

bb

bb

bb bb

bb

b bb

bb

bb

lique stable7

Partition en liques de G ⇐⇒ partition en stables de G

b

b

b bb

bb bb

bb

b bb b

bb b

χ(G ) = χ(G )b

bb

bb

bb

b 8

Partition en liques de G ⇐⇒ Coloration de G

b

b

b bb

bb bb

bb

b bb b

bb b

χ(G ) = χ(G )b

bb

bb

bb

bbb

bb

bb

bb bb

bb 9

Problème : partition en liquesDonnées : Graphe G , entier kQuestion : ∃ partition de G en au plus k liques ?

10

Problème : partition en liquesDonnées : Graphe G , entier kQuestion : ∃ partition de G en au plus k liques ?Complexité : NP

10

Problème : partition en liquesDonnées : Graphe G , entier kQuestion : ∃ partition de G en au plus k liques ?Complexité : NP-omplet

10

L'inégalité χ(G ) ≥ α(G )

11

L'inégalité χ(G ) ≥ α(G )◮ Pas toujours serrée :

12

L'inégalité χ(G ) ≥ α(G )◮ Pas toujours serrée : χ(C5) = 3 > 2 = α(C5)

12

L'inégalité χ(G ) ≥ α(G )◮ Pas toujours serrée : χ(C5) = 3 > 2 = α(C5)◮ Deider si χ(G ) = α(G ) est NP-omplet

12

L'inégalité χ(G ) ≥ α(G )◮ Pas toujours serrée : χ(C5) = 3 > 2 = α(C5)◮ Deider si χ(G ) = α(G ) est NP-omplet◮ Trouver

◮ partition min en liques◮ stable maxNP-di�iles même si χ(G ) = α(G ) 12

Graphes parfaits : passé...◮ Def : Berge 1960Tout sous-graphe induit H de G véri�e χ(H) = α(H)

13

Graphes parfaits : passé...◮ Def : Berge 1960Tout sous-graphe induit H de G véri�e χ(H) = α(H)

PARFAIT

SANS-P4

INTERVALLESBIPARTI

COMPARABILITE TRIANGULE

13

Graphes parfaits : passé, présent...◮ Def : Berge 1960Tout sous-graphe induit H de G véri�e χ(H) = α(H)◮ Optimisation Grötshel, Lovász, Shrijver 1984Partition min en liques et stable max sont polynomiaux

13

Graphes parfaits : passé, présent...◮ Def : Berge 1960Tout sous-graphe induit H de G véri�e χ(H) = α(H)◮ Optimisation Grötshel, Lovász, Shrijver 1984Partition min en liques et stable max sont polynomiaux◮ SPGT Chudnovsky, Robertson, Seymour, Thomas 2002Conjeture forte des graphes parfaits Berge 1960G parfait ⇐⇒ ni trou impair, ni antitrou impair

13

Graphes parfaits : passé, présent...◮ Def : Berge 1960Tout sous-graphe induit H de G véri�e χ(H) = α(H)◮ Optimisation Grötshel, Lovász, Shrijver 1984Partition min en liques et stable max sont polynomiaux◮ SPGT Chudnovsky, Robertson, Seymour, Thomas 2002Conjeture forte des graphes parfaits Berge 1960G parfait ⇐⇒ ni trou impair, ni antitrou impairTrou impair Antitrou impair

13

Graphes parfaits : passé, présent...◮ Def : Berge 1960Tout sous-graphe induit H de G véri�e χ(H) = α(H)◮ Optimisation Grötshel, Lovász, Shrijver 1984Partition min en liques et stable max sont polynomiaux◮ SPGT Chudnovsky, Robertson, Seymour, Thomas 2002Conjeture forte des graphes parfaits Berge 1960G parfait ⇐⇒ ni trou impair, ni antitrou impairTrou impair Antitrou impair◮ Reonnaissane polynomialeChudnovsky, Cornuéjols, Liu, Seymour, Vu²kovi¢ 2005 13

Futur des graphes parfaits : ordonnanement hromatique◮ Appliations de oloration =⇒ ontraintes supplémentaires

14

Futur des graphes parfaits : ordonnanement hromatique◮ Appliations de oloration =⇒ ontraintes supplémentaires◮ Contraintes étudiées en ordonnanement

14

Futur des graphes parfaits : ordonnanement hromatique◮ Appliations de oloration =⇒ ontraintes supplémentaires◮ Contraintes étudiées en ordonnanement◮ Nouveaux problèmes NP-di�iles dans les graphes parfaits...

14

Futur des graphes parfaits : ordonnanement hromatique◮ Appliations de oloration =⇒ ontraintes supplémentaires◮ Contraintes étudiées en ordonnanement◮ Nouveaux problèmes NP-di�iles dans les graphes parfaits...◮ ...mais polynomiauxdans sous-lasses importantes pour appliations

14

Futur des graphes parfaits : ordonnanement hromatique◮ Appliations de oloration =⇒ ontraintes supplémentaires◮ Contraintes étudiées en ordonnanement◮ Nouveaux problèmes NP-di�iles dans les graphes parfaits...◮ ...mais polynomiauxdans sous-lasses importantes pour appliations

+ Relations min-max qui généralisent χ(G ) ≥ α(G )14

II) Extension de pré-partition en liques15

L'ubiquité des ontraintes de pré-a�etation1 53 4 14 6 2 95 6 3 175 92 77 9 216

L'ubiquité des ontraintes de pré-a�etation1 53 4 14 6 2 95 6 3 175 92 77 9 2◮ Sudoku : extension d'une pré-oloration 16

L'ubiquité des ontraintes de pré-a�etation1 53 4 14 6 2 95 6 3 175 92 77 9 2◮ Sudoku : extension d'une pré-oloration d'un graphe◮ 81 sommets 16

L'ubiquité des ontraintes de pré-a�etation1 53 4 14 6 2 95 6 3 175 92 77 9 2◮ Sudoku : extension d'une pré-oloration d'un graphe◮ 81 sommets◮ même ligne, olonne ou arré =⇒ arête 16

[PrExt℄ : extension de pré-partition en liquesDonnées : Graphe G , entier k ,famille de liques disjointes Q = {Q1,Q2, . . .} de GQuestion : ∃ partition de G en k liques qui étende Q ?

17

[PrExt℄ : extension de pré-partition en liquesDonnées : Graphe G , entier k ,famille de liques disjointes Q = {Q1,Q2, . . .} de GQuestion : ∃ partition de G en k liques qui étende Q ?Complexité : NP17

[PrExt℄ : extension de pré-partition en liquesDonnées : Graphe G , entier k ,famille de liques disjointes Q = {Q1,Q2, . . .} de GQuestion : ∃ partition de G en k liques qui étende Q ?Complexité : NP-omplet même dans les graphes parfaits17

[PrExt℄ : la tehnique de ontration◮ Pour un graphe G et une pré-partition Q de G

18

[PrExt℄ : la tehnique de ontration◮ Pour un graphe G et une pré-partition Q de G◮ Contrater haque lique de Q en un sommet

18

[PrExt℄ : la tehnique de ontration◮ Pour un graphe G et une pré-partition Q de G◮ Contrater haque lique de Q en un sommet◮ E�aer arêtes entre pré-liques

18

[PrExt℄ : la tehnique de ontration◮ Pour un graphe G et une pré-partition Q de G◮ Contrater haque lique de Q en un sommet◮ E�aer arêtes entre pré-liques◮ Voisinage d'une pré-lique := {Voisins ommuns}

18

[PrExt℄ : un erti�at d'optimalité

19

[PrExt℄ : le lemme de ontration

◮ Bijetion entre◮ partitions en liques de G qui étendent Q◮ partitions en liques de GQ 20


◮ Bijetion entre◮ partitions en liques de G qui étendent Q◮ partitions en liques de GQ

◮ Def : G est PrExt-parfait si GQ est parfait pour tout Q 20


◮ Bijetion entre◮ partitions en liques de G qui étendent Q◮ partitions en liques de GQ

◮ Def : G est PrExt-parfait si GQ est parfait pour tout Q◮ Hujter, Tuza 1996PrExt-parfait ⊃ split, sans-P4, bipartis-sans-P5, o-bipartis◮ Hertz 1989 GQ est parfait si G est Meyniel et |Qi | = 1 ∀ i 20

Les graphes PrExt-parfaits : la apture du taureau◮ Def : G est PrExt-parfait si GQ est parfait pour tout Q

21

Les graphes PrExt-parfaits : la apture du taureau◮ Def : G est PrExt-parfait si GQ est parfait pour tout Q◮ Par la queue : minimaux non-PrExt-parfaits

21


◮ trous impairs. . .

21


◮ trous impairs,◮ maisons. . .

21


◮ trous impairs, maisons. . .

21


◮ trous impairs, maisons◮ et 'est tout ! Jost, Lévêque, Ma�ray 2005

21


◮ trous impairs, maisons◮ et 'est tout ! Jost, Lévêque, Ma�ray 2005G est PrExt-parfait ⇐⇒ G est un graphe de Meyniel 21


◮ trous impairs, maisons◮ et 'est tout ! Jost, Lévêque, Ma�ray 2005G est PrExt-parfait ⇐⇒ G est un graphe de Meyniel[PrExt℄ est polynomial sur les graphes de Meyniel 21

Complexité de [PrExt℄ sur lasse ( C | C )PARFAIT

SANS-P4

SPLIT

PERMUTATION

INTERVALLES

BIPARTI

FORET

LGBIP

MEYNIEL

PolynomialNP-omplet PrExt-parfait 22

III) Partition en liques bornées23

[PCliqB℄ : partition en liques de taille bornéeDonnées : Graphe G , entiers b et kQuestion : ∃ partition de G en k liques ayant au plus b sommets ?

24

[PCliqB℄ : partition en liques de taille bornéeDonnées : Graphe G , entiers b et kQuestion : ∃ partition de G en k liques ayant au plus b sommets ?Complexité : NP

24

[PCliqB℄ : partition en liques de taille bornéeDonnées : Graphe G , entiers b et kQuestion : ∃ partition de G en k liques ayant au plus b sommets ?Complexité : NP-omplet, même dans les graphes parfaits

24

[PCliqB℄ : un erti�at d'optimalité

25

[PCliqB℄ : un erti�at d'optimalité

C1(U),C2(U), . . .Ct(U) := omposantes onnexes de G [U]σb(G ):= maxU⊆V t∑i=1 ⌈ |Ci (U)|b ⌉ 25

[PCliqB℄ : la formule de �Berge-Tutte-Gallai mod-b�◮ Finke, Jost, Seb®, Queyranne 2004On a toujours

χb(G ) ≥ σb(G ) := maxU⊆V ∑i ⌈ |Ci(U)|b ⌉

26


χb(G ) ≥ σb(G ) := maxU⊆V ∑i ⌈ |Ci(U)|b ⌉◮ Cas ave égalité :

◮ χ(G ) = α(G ) (⇐ {G parfait, b ≥ |V |})26



◮ χ(G ) = α(G ) (⇐ {G parfait, b ≥ |V |})◮ �Berge-Tutte� pour ouplage max (⇐⇒ b = 2)

26



◮ χ(G ) = α(G ) (⇐ {G parfait, b ≥ |V |})◮ �Berge-Tutte� pour ouplage max (⇐⇒ b = 2)◮ Pour tout b : intervalles, triangulés, bipartis, o-LGBIP. . . 26



◮ χ(G ) = α(G ) (⇐ {G parfait, b ≥ |V |})◮ �Berge-Tutte� pour ouplage max (⇐⇒ b = 2)◮ Pour tout b : intervalles, triangulés, bipartis, o-LGBIP. . .

◮ Def : G est borné-parfait si χb(H) = σb(H)pour tout b et tout sous-graphe induit H de G 26

Graphes bornés-parfaits : la apture du taureau◮ Def : G est borné-parfait si pour tout b et tout U ⊆ V

χb(G [U]) = σb(G [U])

27


χb(G [U]) = σb(G [U])◮ Par les ornes : propriétés des bornés-parfaits◮ Par la queue : minimaux non-bornés-parfaits

27


χb(G [U]) = σb(G [U])◮ Par les ornes : propriétés des bornés-parfaits

◮ ⊃ parfaits-sans-{K3 + v} De Werra 85. Gardi 04bb

b bb

bb

b

K3 + vb

bb b

b

b

K1,327



◮ ⊃ parfaits-sans-{K3 + v} De Werra 85. Gardi 04◮ ⊃ parfaits-sans-K4 Hansen, Hertz, Kuplinski 93. FJQS 04

b b

b bb

bb

b

b

b

b

b

b

b

K427



◮ ⊃ parfaits-sans-{K3 + v} De Werra 85. Gardi 04◮ ⊃ parfaits-sans-K4 Hansen, Hertz, Kuplinski 93. FJQS 04◮ ⊃ triangulés Jost 05

b bb

bbb

b

b

C4b

bb

bb

bb

bbb

C5 27



◮ ⊃ parfaits-sans-{K3 + v} De Werra 85. Gardi 04◮ ⊃ parfaits-sans-K4 Hansen, Hertz, Kuplinski 93. FJQS 04◮ ⊃ triangulés Jost 05

◮ Par la queue : minimaux non-bornés-parfaits◮ trous impairs et leurs ompléments

27

Graphes bornés-parfaits : la apture du taureau◮ Par les ornes : propriétés des bornés-parfaits

◮ ⊃ parfaits-sans-{K3 + v}, parfaits-sans-K4, triangulés◮ Par la queue : minimaux non-bornés-parfaits

◮ trous impairs et leurs ompléments◮ antennes

b

b

b bb

bb bb

bb

b

b

b

bb b b

b

b C2ks ta bz

b

b

b bb

bb bb

bb

b

b

b

bb b b

b

b C2ks ta bz

b

b

b

b

b bb

b

b

b

b b

b

bb

b

b bb b

s ta bz C2k

Ann02k Ann12k Ann22k 27

[PCliqB℄ : un algorithme glouton pour les intervalles◮ Trier par ordre roissant des �ns d'intervallesI1 b bI2 b bI3 b bI4 b bI5 b bI6 b bI7 b bI8 b bI9 b bI10 b bI11 b bIntervalles

Extrémités 28

[PCliqB℄ : un algorithme glouton pour les intervalles◮ Les intervalles ompatibles ave I1I1 b bI2 b bI3 b bI4 b bI5 b bI6 b bI7 b bI8 b bI9 b bI10 b bI11 b bIntervalles

Extrémités 28

[PCliqB℄ : un algorithme glouton pour les intervalles◮ Un hoix glouton pour la lique ontenant I1 (b = 3)I1 b bI2 b bI3 b bI4 b bI5 b bI6 b bI7 b bI8 b bI9 b bI10 b bI11 b b

B1 = {I1, I2, I3}IntervallesExtrémités 28

[PCliqB℄ : un algorithme glouton pour les intervalles◮ Après l'entrée, le gratin Dauphinois ! (b = 3)I1 b bI2 b bI3 b bI4 b bI5 b bI6 b bI7 b bI8 b bI9 b bI10 b bI11 b b

B1 = {I1, I2, I3}B2 = {I4, I5, I7}IntervallesExtrémités 28

[PCliqB℄ : un algorithme glouton pour les intervalles◮ Garguantua est repu ! ! ! (b = 3)I1 b bI2 b bI3 b bI4 b bI5 b bI6 b bI7 b bI8 b bI9 b bI10 b bI11 b b

B1 = {I1, I2, I3}B2 = {I4, I5, I7}B3 = {I6, I8, I11}B4 = {I9}B5 = {I10}Intervalles

Extrémités 28

[PCliqB℄ : un algorithme glouton pour les intervalles◮ Solution duale dans la formule de Berge-Tutte-Gallai mod-3

b b

b b

b b

b b

b b

b b

b b

b b

b b

b b

b b

IntervallesExtrémités 28

Complexité de (Coloration | Partition en liques) b-bornéePARFAIT

SANS-P4

GALLAI

TRIANGULE

INTERVALLES

BIPARTI

FORETco-LGBIP

PARFAIT-{K3 + v} PARFAIT-K4

BORNE-PARFAIT

PolynomialNP-omplet Borné-parfait+ polynomial 29

IV) Partition de oût minimum (en liques)30

Combinatoire polyèdrale31

Combinatoire polyèdrale, systèmes TDI et TDAU31

[PCliqW℄ : partition de oût minimum (en liques)Données : graphe G , fontion de oût f : P(V ) → R+(f est donnée par un orale de valeur)Résultat : une partition en liques K = {Q1,Q2, . . .Qk} de GObjetif : minimiser ∑ki=1 f (Qi )Complexité : exponentielle32

[PCliqW℄ : partition de oût minimum (en liques)Données : graphe G , fontion de oût f : P(V ) → R+(f est donnée par un orale de valeur)Résultat : une partition en liques K = {Q1,Q2, . . .Qk} de GObjetif : minimiser ∑ki=1 f (Qi )Complexité : exponentielle(PLNE)

min fyy(v) = 1 pour tout v ∈ VyQ ∈ {0, 1} pour toute lique Q de G32


min fyy(v) = 1 pour tout v ∈ VyQ ∈ {0, 1} pour toute lique Q de G◮ dual de relaxation linéairemax1x(Dual) x(Q) ≤ f (Q) pour toute lique Q de G 32


min fyy(v) = 1 pour tout v ∈ VyQ ∈ {0, 1} pour toute lique Q de G◮ dual de relaxation linéairemax1x(Dual) x(Q) ≤ f (Q) pour toute lique Q de G◮ Paires (G , f ) telles que (Dual) est TDI ou TDAU? 32

[PCliqW℄ : quelques lassiques de la ombinatoire polyèdrale◮ Le système ave variables x ∈ RVx(Q) ≤ f (Q) pour toute lique Q de G

33

[PCliqW℄ : quelques lassiques de la ombinatoire polyèdrale◮ Le système ave variables x ∈ RVx(Q) ≤ f (Q) pour toute lique Q de G◮ est TDI si G est parfait et f ≡ 1 Fulkerson, Lovász 70's

33

[PCliqW℄ : quelques lassiques de la ombinatoire polyèdrale◮ Le système ave variables x ∈ RVx(Q) ≤ f (Q) pour toute lique Q de G◮ est TDI si G est parfait et f ≡ 1 Fulkerson, Lovász 70's◮ est TDAU si G est omplet et f est sous-modulaire(Tronation de Dilworth Edmonds 70)

33

[PCliqW℄ : quelques lassiques de la ombinatoire polyèdrale◮ Le système ave variables x ∈ RVx(Q) ≤ f (Q) pour toute lique Q de G◮ est TDI si G est parfait et f ≡ 1 Fulkerson, Lovász 70's◮ est TDAU si G est omplet et f est sous-modulaire(Tronation de Dilworth Edmonds 70)◮ est TDAU si G est (o-)omparabilité et f ≡ 1Greene, Kleitman, Cameron, Edmonds, Giles 70's 33

[PCliqW℄ : quelques lassiques de la ombinatoire polyèdrale◮ Le système ave variables x ∈ RVx(Q) ≤ f (Q) pour toute lique Q de G◮ est TDI si G est parfait et f ≡ 1 Fulkerson, Lovász 70's◮ est TDAU si G est omplet et f est sous-modulaire(Tronation de Dilworth Edmonds 70)◮ est TDAU si G est (o-)omparabilité et f ≡ 1Greene, Kleitman, Cameron, Edmonds, Giles 70's◮ d'autres as intéressants ? 33

[PCliqW℄ : une hybridation frutueuse mais omplexe◮ Complexité de [PCliqW℄ et as TDI du systèmex(Q) ≤ f (Q) pour toute lique Q de G

34

[PCliqW℄ : une hybridation frutueuse mais omplexe◮ Complexité de [PCliqW℄ et as TDI du systèmex(Q) ≤ f (Q) pour toute lique Q de Gf \ G LGBIP sans-P4 Intervalles Triangulé ParfaitUnitaire P P P P PMax-bath P P * P * NPC NPCSteiner TSP P ? NPC NPC NPCsur un arbreSous-modulaire P * EXP* NPH NPH EXP(modèle orale) 34

[PCliqW℄ : une hybridation frutueuse mais omplexe◮ Complexité de [PCliqW℄ et as TDI du systèmex(Q) ≤ f (Q) pour toute lique Q de Gf \ G LGBIP sans-P4 Intervalles Triangulé ParfaitUnitaire P P P P PMax-bath P P * P * NPC NPCSteiner TSP P ? NPC NPC NPCsur un arbreSous-modulaire P * EXP* NPH NPH EXP(modèle orale)◮ Pont entre relations min-max pour fontions sous-modulaireset graphes parfaits, mais pas de généralisation ommune 34

Apport énergetique◮ Extension de pré-oloration ([PrExt]-parfait = Meyniel)◮ Partition en liques bornées (onjetures borné-parfait)◮ Partition de oût minimum (systèmes TDAU et TDI)

35

Apport énergetique, �bres alimentaires◮ Extension de pré-oloration ([PrExt]-parfait = Meyniel)◮ Partition en liques bornées (onjetures borné-parfait)◮ Partition de oût minimum (systèmes TDAU et TDI)♣ Conjeture de Fraenkel pour les palindr�mes Brauner, Jost 03♣ Ordonnanement juste-à-temps Lebaque, Jost, Brauner 04♣ Cas polynomial de [PCliqW℄ Gijswijt, Jost, Queyranne 06G est d'intervalles et f est valeur-polymatroïdale

35

Apport énergetique, �bres alimentaires et vitamines◮ Extension de pré-oloration ([PrExt]-parfait = Meyniel)◮ Partition en liques bornées (onjetures borné-parfait)◮ Partition de oût minimum (systèmes TDAU et TDI)♣ Conjeture de Fraenkel pour les palindr�mes Brauner, Jost 03♣ Ordonnanement juste-à-temps Lebaque, Jost, Brauner 04♣ Cas polynomial de [PCliqW℄ Gijswijt, Jost, Queyranne 06G est d'intervalles et f est valeur-polymatroïdale♥ Jeux oopératif sur des strutures ombinatoires♥ Classi�ation de problèmes d'ordonnanement hromatique 35

Apport énergetique, �bres alimentaires et vitamines◮ Extension de pré-oloration ([PrExt]-parfait = Meyniel)◮ Partition en liques bornées (onjetures borné-parfait)◮ Partition de oût minimum (systèmes TDAU et TDI)♣ Conjeture de Fraenkel pour les palindr�mes Brauner, Jost 03♣ Ordonnanement juste-à-temps Lebaque, Jost, Brauner 04♣ Cas polynomial de [PCliqW℄ Gijswijt, Jost, Queyranne 06G est d'intervalles et f est valeur-polymatroïdale♥ Jeux oopératif sur des strutures ombinatoires♥ Classi�ation de problèmes d'ordonnanement hromatique♥ Freakombinatoris :

♥ PLNE ave variables sur les arêtes pour oloration Cornaz, Jost♥ PLNE ave variables sur les sommets pour le TSP 35

Apport énergetique, �bres alimentaires et vitamines◮ Extension de pré-oloration ([PrExt]-parfait = Meyniel)◮ Partition en liques bornées (♥ onjetures borné-parfait)◮ Partition de oût minimum (♥ systèmes TDAU et TDI)♣ Conjeture de Fraenkel pour les palindr�mes Brauner, Jost 03♣ Ordonnanement juste-à-temps Lebaque, Jost, Brauner 04♣ Cas polynomial de [PCliqW℄ Gijswijt, Jost, Queyranne 06G est d'intervalles et f est valeur-polymatroïdale♥ Jeux oopératif sur des strutures ombinatoires♥ Classi�ation de problèmes d'ordonnanement hromatique♥ Freakombinatoris :

♥ PLNE ave variables sur les arêtes pour oloration Cornaz, Jost♥ PLNE ave variables sur les sommets pour le TSP 35

Documents

Ordonnancement chromatique - =1=polyèdres, complexité et …vjost/Soutenance_Jost.pdf · 2007. 3. 13. · Ordonnancement chromatique p oly èdres, complexité et classi cation Vincent