Rafael Castro de Andrade (Université de Paris XIII)

DCMST : degree constrained minimum spanning tree problem - problème de l’arbre couvrant de coût minimal avec des contraintes sur le degré des sommets.

Dans mon exposé, je ferai une synthèse des travaux de la littérature pour ce problème, tout en montrant aussi mon heuristique basée sur la relaxation Lagrangienne et sur des méthodes de recherche locale. Je vais montrer une approche de résolution basée sur une réduction de l’espace de solutions réalisables qui a permi de traiter des instances avec des milliers de sommets dans des graphes complets. En outre, je vous presenterai une inégalité (contrainte de degré) pour l’union des sous-arbres réalisables pour ce problème.

D’autre part, je ferai le pont entre les travaux existants dans la Géométrie Discrète et ceux de l’Optimisation Combinatoire. Je montrerai par exemple, les résultats de Papadimitriou et Varirani concernant la complexité du problème, ainsi qu’une conjecture qui reste ensolvable depuis 1984.

Enfin, je montre nos résultats pour les instances DCMST le plus difficiles de la littérature, et pour des graphes à des milliers de sommets.