Algorithmes de couverture et d'augmentation de graphes sous contraintes de distance
Institution:
Aix-Marseille 2Disciplines:
Directors:
Abstract EN:
We study several NP-hard network improvement problems, which consist in adding new links to a network in order to improve its performance and robustness. They are formulated as graph augmentation problems in the following way: add a minimum number of edges to a given graph so that the resulting augmented graph satisfies certain diameter and/or connectivity constraints. Most of these problems are hard to approximate within a constant factor. Nevertheless, in this thesis, we propose constant factor approximation algorithms in several important classes of graphs: trees, planar graphs, graphs of bounded treewidth,[delta]-hyperbolic graphs. Our algorithms derive their solutions by covering the initial graph with a minimum number of balls. For each of these classes of graphs, we present three kinds of results: (i) exact or approximation algorithms for covering with balls, (ii) min-max results which guarantee the quality of the constructed solutions, (iii) methods for deriving a feasible augmentation from a covering with balls of the initial graph. We also solve a conjecture by Gavoille, Peleg, Raspaud, and Sopena (2001) by showing that any planar graph of diameter 2R can be covered with a constant number of balls of radius R.
Abstract FR:
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 [delta]-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.