Augmentation sous contrainte de diametre Couverture Arbres diametre pair D 2R Arbres diametre impair D 2R Perspectives graphes planaires

Augmentation sous contrainte de diametre Couverture Arbres : diametre pair D = 2R Arbres : diametre impair D = 2R + 1 Perspectives : graphes planaires, Augmentation de graphe sous contrainte de diametre V. Chepoi, B. Estellon, K. Nouioua, Y. Vaxes Universite de la Mediterranee Laboratoire d'Informatique Fondamentale de Marseille Equipe Combinatoire et Recherche Operationnelle 23 janvier 2009

• delai maximum de communications


• problemes algorithmiques


• classe complexite des problemes


• diametre pair


• lies aux distances dans les graphes


• graphe planaire


• laboratoire d'informatique fondamentale