Bertrand Estellon (LIF Marseille)

Algorithmes de couverture et d'augmentation de graphes sous contraintes de distance

Nous étudions plusieurs problèmes d'amélioration de réseaux qui consistent 
à ajouter de nouvelles liaisons à un réseau donné afin d'améliorer ses 
performances et sa robustesse. Ces problèmes sont formulés comme des 
problèmes d'augmentation de graphes de la façon suivante : ajouter un nombre 
minimum d'arêtes à un graphe de façon à obtenir un graphe augmenté qui 
satisfasse certaines contraintes de diamètre et/ou de connexité. La plupart 
de ces problèmes sont difficiles à approximer avec un facteur constant. 
Néanmoins, dans cette thèse, nous proposons des algorithmes avec des facteurs 
constants pour certaines classes de graphes importantes : les arbres, les 
graphes planaires, les graphes de largeur arborescente bornée, les graphes 
δ-hyperboliques. Nos algorithmes dérivent leurs solutions en couvrant le 
graphe initial avec un nombre minimum de boules. Pour chacune de ces classes de 
graphes, nous présentons trois types de résultats: (i) des algorithmes exacts 
ou d'approximation pour des problèmes de couverture par des boules, (ii) des 
résultats min-max qui garantissent la qualité des solutions construites, 
(iii) des méthodes pour dériver une augmentation admissible à partir d'une 
couverture du graphe initial par des boules. Nous résolvons aussi une 
conjecture de Gavoille, Peleg, Raspaud et Sopena (2001) en montrant que tout 
graphe planaire de diamètre 2R peut être couvert par un nombre constant de 
boules de rayon R.

Mots-clés : graphe, algorithme d'approximation, problème d'augmentation, couverture par des boules, distance, connexité.

Page web : http://pageperso.lif.univ-mrs.fr/~bertrand.estellon/