Séminaire du LIF
Jeudi 19 décembre à 14h - Luminy, Amphi 12
Gérard Cornuejols
LIF, PR Associé, Aix-Marseille 2
Un algorithme polynomial pour la reconnaissance des graphes parfaits
Ce résultat a été obtenu en collaboration avec Paul Seymour et Maria Chudnovsky (Université de Princeton), Kristina Vuskovic (Université de Leeds) et Xinming Liu (Université de Carnegie Mellon).
L'algorithme de reconnaissance est en deux phases. Dans la première phase, on "nettoie" le graphe en temps polynomial et, ce faisant, il se peut que l'on découvre déjà que le graphe n'est pas parfait. La deuxième phase est un algorithme polynomial pour trouver un trou impair dans un graphe nettoyé. Le théorème fort des graphes parfaits montre qu'il suffit d'appliquer la deuxième phase au graphe et à son complement.
Home page : http://www.math.cmu.edu/people/fac/cornuejols.html
The Strong Perfect Graph Conjecture, by Gerard Cornuejols. In Proceedings of the International Congress of Mathematicians III: Invited Lectures , Beijing (2002) 547-559. http://integer.gsia.cmu.edu/webpub/SPGCsurvey.pdf