Aller au menu Aller au contenu
Consultez les publications et les thèses
Laboratoire des Sciences pour la Conception, l'Optimisation et la Production de Grenoble
Consultez les publications et les thèses
Consultez les publications et les thèses

> GSCOP_RESULTATS > GSCOP_ThèsesSoutenues

Thèse Roland GRAPPE

Auteur : Roland GRAPPE
Directeur de thèse : Zoltan SZIGETI
Date : 04 Décembre 2009

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.

Mots clés : arête-connexité, graphes, hypergraphes, fonctions sous-modulaires.

mise à jour le 4 juin 2012

  • Tutelle CNRS
  • Tutelle Grenoble INP
  • Université Joseph Fourier
  • Tutelle UMR
Univ. Grenoble Alpes