Dans cette thèse, nous étudions des problèmes différents de coloration maximale dans les graphes sommet-colorés. Nous nous concentrons sur la recherche des structures avec le nombre maximal possible de couleurs par des algorithmes en temps polynomial, nous donnons aussi la preuve des problèmes NP-difficiles pour des graphes spécifiques. En particulier, nous étudions d’abord le problème de l’appariement coloré maximum. Nous montrons que ce problème peut être résolu efficacement en temps polynomial. En plus, nous considérons également une version spécifique de ce problème, à savoir l’appariement tropical, qui consiste à trouver un appariement contenant toutes les couleurs du graphe original. De même, un algorithme de temps polynomial est également fourni pour le problème de l’appariement tropical avec la cardinalité minimale et le problème de l’appariement tropical maximum avec la cardinalité minimale. Ensuite, nous étudions le problème des chemins colorés maximum. Il existe deux versions pour ce problème: le problème de plus court chemin tropical, c’est-à-dire de trouver un chemin tropical avec le poids total minimum et le problème de plus longue chemin coloré, à savoir, trouver un chemin avec un nombre maximum possible de couleurs. Nous montrons que les deux versions de ce problème sont NP-difficile pour un graphe orienté acyclique, graphes de cactus et graphes d'intervalles où le problème de plus long chemin est facile. De plus, nous fournissons également un algorithme de paramètre fixe pour le premier dans les graphes généraux et plusieurs algorithmes de temps polynomiaux pour le second dans les graphes spécifiques, y compris les graphes des chaîne bipartites, graphes de seuil, arborescences, graphes des blocs et graphes d'intervalles appropriés. Ensuite, nous considérons le problème des cycles colorés maximum. Nous montrons d'abord que le problème est NP-difficile même pour des graphes simples tels que des graphes divisés, des graphes bi-connecteurs et des graphes d'intervalles. Nous fournissons ensuite des algorithmes de temps polynomial pour les classes de graphes de seuil et graphes des chaîne bipartites et graphes d'intervalles appropriés. Plus tard, nous étudions le problème des cliques colorées maximum. Nous montrons tout d’abord que le problème est NP-difficile même pour plusieurs cas où le problème de clique maximum est facile, comme des graphes complémentaires des graphes de permutation bipartite, des graphes complémentaires de graphes convexes bipartites et des graphes de disques unitaires, et aussi pour des graphes sommet-colorées appropriés. Ensuite, nous proposons un algorithme paramétré XP et des algorithmes de temps polynomial pour les classes de graphes complémentaires de graphes en chaîne bipartites, des graphes multipartites complets et des graphes complémentaires de graphes cycles. Enfin, nous nous concentrons sur le problème des stables (ensembles indépendants) colorés maximum. Nous montrons d’abord que le problème est NP-difficile même dans certains cas où le problème de stable maximum est facile, tels que les co-graphes et les graphes des P₅-gratuit. Ensuite, nous fournissons des algorithmes de temps polynomial pour les graphes de grappes, et les arbres. / In this thesis, we study different maximum colorful problems in vertex-colored graphs. We focus on finding structures with the possible maximum number of colors by efficient polynomial-time algorithms, or prove these problems as NP-hard for specific graphs. In particular, we first study the maximum colorful matching problem. We show that this problem can be efficiently solved in polynomial time. Moreover, we also consider a specific version of this problem, namely tropical matching, that is to find a matching containing all colors of the original graph, if any. Similarly, a polynomial time algorithm is also provided for the problem of tropical matching with the minimum cardinality and the problem of maximal tropical matching with the minimum cardinality. Then, we study the maximum colorful paths problem. There are two versions for this problem: the shortest tropical path problem, i.e., finding a tropical path with the minimum total weight, and the maximum colorful path problem, i.e., finding a path with the maximum number of colors possible. We show that both versions of this problem are NP-hard for directed acyclic graphs, cactus graphs and interval graphs where the longest path problem is easy. Moreover, we also provide a fixed parameter algorithm for the former in general graphs and several polynomial time algorithms for the latter in specific graphs, including bipartite chain graphs, threshold graphs, trees, block graphs, and proper interval graphs. Next we consider the maximum colorful cycles problem. We first show that the problem is NP-hard even for simple graphs such as split graphs, biconnected graphs, interval graphs. Then we provide polynomial-time algorithms for classes of threshold graphs and bipartite chain graphs and proper interval graphs. Later, we study the maximum colorful cliques problem. We first show that the problem is NP-hard even for several cases where the maximum clique problem is easy, such as complement graphs of bipartite permutation graphs, complement graphs of bipartite convex graphs, and unit disk graphs, and also for properly vertex-colored graphs. Next, we propose a XP parameterized algorithm and polynomial-time algorithms for classes of complement graphs of bipartite chain graphs, complete multipartite graphs and complement graphs of cycle graphs. Finally, we focus on the maximum colorful independent set problem. We first prove that the problem is NP-hard even for some cases where the maximum independent set problem is easy, such as cographs and P₅-free graphs. Next, we provide polynomial time algorithms for cluster graphs and trees.
| Identifer | oai:union.ndltd.org:theses.fr/2018SACLS528 |
| Date | 07 December 2018 |
| Creators | Pham, Hong Phong |
| Contributors | Université Paris-Saclay (ComUE), Manoussakis, Yannis |
| Source Sets | Dépôt national des thèses électroniques françaises |
| Language | English |
| Detected Language | French |
| Type | Electronic Thesis or Dissertation, Text |
Page generated in 0.0028 seconds