Contribution to graph algorithm: some useful graphs' representations
Contribution à l'algorithmique des graphes: quelques représentations pertinentes de graphes
Résumé
Ce document est divisé en deux parties principales. La première partie concerne les résultats que nous avons obtenu au travers de diverses collaborations sur les communications dans les réseaux. Afin de ne pas multiplier les chapitres dans cette partie, nous avons choisi en premier lieu de présenter l'évolution du contexte des réseaux sur lesquels j'ai travaillé durant ces 10 dernières années. En particulier, nous montrons plusieurs facettes que peut recouvrir l'expression \textbf{communications optiques}. Dans un deuxième temps, nous avons regroupé les problèmes abordés en deux chapitres: - le premier s'intéresse à des aspects structurels des graphes utiles pour la construction de protocoles de communication dans les réseaux. - le second aborde une problématique importante dans le contexte actuel de la recherche de la compétitivité: l'optimisation de ressources. La deuxième partie s'intéresse à deux représentations de graphes qui s'avèrent pertinentes pour les problèmes considérés. Elle présente deux problèmes principaux donnant deux chapitres indépendants. Le premier problème abordé dans cette partie concerne un très vieux (au sens informatique) problème issu de la théorie de flots: les flots multi-terminaux. Nous nous sommes attachés à montrer la puissance d'un outil permettant de représenter ces types de flots: les arbres de Gomory-Hu, ainsi que leur utilité dans une version paramétrée du problème. Le second problème présente au travers du calcul du polynôme chromatique une représentation des graphes sous la forme d'arbre de cliques augmenté.