Retour à l'index du GREYC

Séminaire Algorithmique

Site du CNRS

Séminaire Algorithmique

Le séminaire a lieu le mardi à 11 h 45 (sauf modification exceptionnelle), au campus Côte de Nacre, bâtiment Sciences 3, salle S3 351, 3ème étage.

Résumé du séminaire du Mardi 23 Mars 2004

Complexité et heuristiques pour le DCMST

par 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.

GREYC
Campus Côte de Nacre, boulevard du Maréchal Juin
BP 5186
14032 Caen Cedex
FAX : +33 (0)2 31 56 73 30
http://www.greyc.fr