Ph.D
Group : Graphs, ALgorithms and Combinatorics
EStudies on Optimal Colorful Structures in Vertex-Colored Graphs
Starts on 01/11/2015
Advisor : MANOUSSAKIS, Yannis
Funding : Contrat doctoral uniquement recherche
Affiliation : Université Paris-Saclay
Laboratory : LRI - GALaC
Defended on 07/12/2018, committee :
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
Research activities :
Abstract :
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.