Jack Edmonds : la révélation de la complexité
Le mathématicien américain Jack Edmonds est né en 1934. Après ses études, il entre au National Bureau of Standards, où il travaille sur la coloration des graphes, qu’il représente au moyen de cartes et de brins. À la frontière des années 1950 et 1960, l’étude des graphes est passée du stade des « problèmes plaisants et délectables » à celui de sujet académique (voir Mathématiques discrètes et Combinatoire, Bibliothèque Tangente 39, 2009).
Claude Berge décrit la méthode des chaînes alternées pour les problèmes de couplages de cardinal maximum. Dans un fameux congrès à Calgary (Canada), il présente cet « algorithme ». Jack au milieu de la salle se lève et dit : « Claude it stinks your algorithm » (« Il pue, ton algorithme »). Jack, pour ce même problème, utilise les arbres alternés ainsi que la dualité des programmes linéaires. Ses arbres ne sont pas de tout repos, ils peuvent contenir des cycles impairs, qu’il va « shrinker » (condenser) en un point, et ainsi de suite, ce qui le conduit à un algorithme polynomial. Le mot est lâché. Dans la nuit qui précède son propre exposé, il veut généraliser son algorithme à la recherche d’un ensemble de sommets d’un graphe deux à ...
Lire la suite gratuitement