Français Anglais
Accueil Annuaire Plan du site
Accueil > Production scientifique > Thèses et habilitations
Production scientifique
Doctorat de

Doctorat
Equipe : Graphes, Algorithmes et Combinatoire

Algorithmes Combinatoires et Optimisation

Début le 01/12/2014
Direction : DEZA, Antoine
[COHEN Johanne]

Ecole doctorale : ED STIC 580
Etablissement d'inscription : Université Paris-Sud

Lieu de déroulement : LRI - GALaC

Soutenue le 15/11/2017 devant le jury composé de :
Co-directrice de thèse :
- Johanne Cohen, Paris-Sud;
Co-directeur de thèse
- Antoine Deza,Paris-Sud.

Raporteurs :
- Ralf Klasing, Bordeaux;
- Dmitri Pasechnik, Oxford;
- Lionel Pournin, Paris XIII.

Examinateurs :
- Ioan Todinca, Orléans;
- Michele Sebag, Paris-Sud;
- Cristina Bazgan, Université Paris-Dauphine.

Activités de recherche :

Résumé :
Nous nous intéressons à trois questions principales dans ce document.
Les deux premières concernent des problèmes d'algorithmique de
graphe. Nous introduisons d'abord la classe des graphes k-dégénérés qui
sont souvent utilisés pour modéliser des graphes éparses issus du monde
réel. Nous proposons de nouveaux algorithmes d'énumération pour ces
graphes. En particulier, nous construisons un algorithme énumérant
tous les cycles de tailles xés dans ces graphes, en temps optimal, ainsi
qu'un algorithme output sensitif pour l'énumération de toutes leurs
cliques maximales.
La seconde question que nous étudions est aussi une question d'algorithmique
de graphes, bien que le contexte soit diérent. Nous consid
érons les graphes en tant qu'objets distribués. Chaque sommet a
une capacité de calcul et peut communiquer avec ses voisins. Dans ce
contexte, nous nous intéressons à des questions liées à la notion de couplage.
Nous ne faisons aucune supposition sur l'état initial du système
qui peut donc être correct ou incorrect. Des algorithmes distribués fonctionnant
sous cette hypothèses sont appelés auto-stabilisant. Dans ce
cadre nous proposons un algorithme retournant une 2=3-approximation
du couplage maximum ainsi qu'un algorithme retournant un couplage
maximal quand les communications sont restreintes de telle manière à
simuler le paradigme du passage de message.
Le troisième objet d'étude n'est pas directement lié à l'algorithmique
de graphe, bien que quelques techniques classiques de ce domaine
soient utilisées pour obtenir certains de nos résultats. Nous introduisons
et étudions certaines familles de polytopes, appelées zonotopes
primitifs, qui peuvent être décrits comme la somme de Minkowski de
vecteurs primitifs. Nous prouvons certaines de leurs propriétés combinatoires
et illustrons la connexion avec le plus grand diamètre possible
de l'enveloppe convexe de points à coordonnées entières à valeurs dans
[k], en dimension d.