Thèse Roland GRAPPE

Augmentation de l'arête-connexité

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é étudié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.