Résumé de séminaire

Résumé :

Dans un graphe, un trou est un circuit induit. Il y a une dizaine d'années, Bienstock a démontré que, étant donnés un graphe G et un sommet v de G, il est NP-complet de déterminer s'il existe un trou pair de G passant par v. Par contraste, nous donnons un algorithme polynomial pour déterminer si un graphe G contient un trou pair. Ce résultat a été obtenu en collaboration avec Michele Conforti, Ajai Kapoor et Kristina Vuskovic.

Références :

Home page : http://www.math.cmu.edu/people/fac/cornuejols.html