du 18 au 22 janvier 2010 — ENS Lyon
Intervenants :
- L. Esperet (7h)
- F. Maffray (6h)
- M. Preissmann (5h)
- A. Sebo (6h)
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)