du 18 au 22 janvier 2010 — ENS Lyon

Intervenants :

Lieu des cours et emploi du temps

Tous les cours auront lieu dans l’amphithéatre B, au 3ème étage du bâtiment GN1 (bâtiment principal du site « Sciences » de l’ENS Lyon), ENS Lyon, 46 allée d’Italie, Lyon 7ème.

Lundi : Frédéric Maffray (9h30-12h45) ; Louis Esperet (14h-17h15)
Mardi : Louis Esperet (8h-10h) ; Andras Sebö (10h15-12h15)
Mercredi : Andras Sebö (8h-10h) ; Myriam Preissmann (10h15-12h15) ; Andras Sebö (14h-16h)
Jeudi : Myriam Preissmann (9h30-12h45)
Vendredi : Frédéric Maffray (9h30-12h45) ; Louis Esperet (14h-16h)

Louis Esperet (slides -> cours1, cours2)

Cours 1 (Lundi 14h-17h15) Coloration vs. coloration par listes

  • méthodes inductives (Thomassen)
  • déchargement

Cours 2 (Mardi 8h-10h) Graphes sans triangles et coloration

  • constructions
  • méthodes probabilistes (premier moment)

Cours 3 (Vendredi 14h-16h) Coloration fractionnaire, coloration d’hypergraphes

  • méthodes algébriques (Borsuk-Ulam)
  • méthodes probabilistes (Lemme Local de Lovasz)

Frédéric Maffray (fiche exercices -> télécharger Fiche)

Cours 1 (Lundi 9h30-12h45):

  • Introduction du concept de graphes parfaits
  • Graphes triangulés, décomposition par clique d’articulation, sommets simpliciaux, ordre d’élimination, algorithme MCS,
  • utilisation de ces structures pour résoudre les problèmes d’optimisation (coloration, clique max, stable max).
  • Représentation d’un triangulé comme graphe d’intersection de sous-arbres d’un arbre.
  • Exemples de graphes triangulés: graphes d’intervalles, graphes “splits”.

Cours 2 (Vendredi 9h30-12h45):

  • Relation entre nombre chromatique et orientation (Gallai-Roy)
  • graphes de comparabilité, ensembles partiellement ordonnés,théorème de Dilworth.
  • théorème de Lovasz (parfait = complémentaire de parfait)

Myriam Preissmann

Cours 1 (Mercredi 10h15-12h15) :

  • Flot maximum
  • Algorithme “Push-Relabel” et flots paramétriques.
  • Calcul de l’arête-connectivité d’un graphe non orienté avec, et sans calcul de flot max.

Cours 2 (Jeudi 9h30-12h45) :

  • Flot de coût minimum.
  • Les k-flots non nuls.
  • Théorème du 8-flot.

Andras Sebö (fiches d’exercices -> télécharger Fiche 1, Fiche 2)

Cours 1 Mardi (10h15-12h15)

  • Quelques modèles d’optimisation combinatoire.
  • Matroïdes, algorithme glouton et polytôpe associé.

Cours 2 (Mercredi 8h-10h)

  • Algorithme de l’intersection de deux matroïdes.
  • Applications.

Cours 3 (Mercredi 14h-16h)

  • Algorithme de couplage de cardinalité maximum (Edmonds).
  • Théorème de caractérisation lié (Tutte-Berge).
  • Applications et généralisations.

S’il y a des questions sur les exercices de la fiche fournie ci-dessus, vous pourrez les poser après le premier cours.

Bibliographie : Schrijver: Combinatorial Optimization; Lovász, Plummer: MatchingTheory; Lovasz: Combinatorial Problems and Exercises,

Autres informations pratiques

Voir la page des Ecoles du Master d’Informatique.

Correspondant local

Eric Thierry (prenom.nom@ens-lyon.fr)