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

Etude topologique et algorithmique des structures tropicales dans les graphes sommet-coloriés

Début le 01/11/2015
Direction : MANOUSSAKIS, Yannis

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

Lieu de déroulement : LRI - GALaC

Soutenue le 07/12/2018 devant le jury composé de :
Directeur de thèse :
- Yannis MANOUSSAKIS, Université Paris-Sud

Rapporteurs :
- Mathieu LIEDLOFF, Université d'Orléans
- George MERTZIOS, Durham University

Examinateurs :
- Cristina BAZGAN, Université Paris Dauphine
- Marc BABOULIN, Université Paris-Sud
- Johanne COHEN, Université Paris-Sud

Activités de recherche :

Résumé :
In this thesis, we study several different maximum colorful problems in vertex-colored graphs. In other words, we focus on finding popular structures such as matchings, paths, cycles, cliques and independent sets with the possible maximum number of colors by polynomial-time algorithms, or prove that these problems are NP-hard. Moreover, we also proposed efficient algorithms for these problems for some kinds of specific graphs where these problems are still NP-hard.