Augmentation de l'arête-connexité
Institution:
Grenoble INPGDisciplines:
Directors:
Abstract EN:
A graph is k-edge-connected if removing less than k edges does not disconnect it. The problem of edge-connectivity augmentation of a graph is as follows : given a graph and a integer k, add a minimum number of edges to make the graph k-edge-connected. Since the problem was solved, many variants have been studied : for example edge-connectivity augmentation of a graph with partition constraints : edge-connectivity augmentation of a hypergraph : or problems of covering a function by a graph, abstract generalizations of the augmentation problems. The aim of this thesis is to unify various results of the field. First we solve the problem of edge-connectivity augmentation of a hypergraph with partition contraints, and then its abstract form, the partition constrainedcovering af a symmetric crossing supermodular function. Finally, we solve the covering of a symmetric semi-monotone function.
Abstract FR:
Un graphe est k-arête-connexe si lui retirer moins de k arêtes ne le déconnecte pas. L'augmentation de l'arête-connexité d'un graphe consiste à, étant donné un entier k et un graphe, ajouter un nombre minimal d'arêtes au graphe afin de la rendre k-arête-connexe. Depuis la résolution de ce problème, de nombreuses variantes ont été etudiées : par exemple l'augmentation de l'arête-connexité d'un graphe sous contraintes de partition ; l'augmentation de l'arête-connexité d'un hypergraphe ; ou encore les problèmes de recouvrement de fonctions, généralisations abstraites des problèmes d'augmentation. Le but de cette thèse est d'unifier différents résultats du domaine. Nous y résolvons d'abord l'augmentation de l'arête-connexité d'un hypergraphe sous contraintes de partition, puis sa généralisation abstraite, le recouvrement d'une fonction symétrique surmodulaire croisée sous contraintes de partition. Finalement, nous résolvons le recouvrement d'une fonction symétrique semi-monotone.