Spelling suggestions: "subject:"sousgraphes induit"" "subject:"sousgraphes induite""
1 |
Multicoupes et sous-graphes induits : complexité et algorithmes.Derhy, Nicolas 04 December 2008 (has links) (PDF)
Dans ce travail de thèse, nous nous intéressons à plusieurs problèmes de théorie des graphes. Dans un premier temps, nous étudions différents problèmes de coupes et de multicoupes puis, dans un second temps, nous nous focalisons sur des problèmes de recherche de sous-graphes induits. Néanmoins, ces deux parties suivent la même ligne directrice : donner une vue d'ensemble de la complexité des problèmes en établissant leur NP-complétude ou en déterminant un algorithme polynomial de moindre complexité. Dans la première partie de la thèse, nous abordons les problèmes de coupes et de multicoupes. Tout d'abord, nous étudions la conséquence de l'ajout d'une contrainte de cardinalité à ces deux types de problèmes et démontrons leur NP- complétude dans le cas général. Puis, nous déterminons leur complexité dans plusieurs classes de graphes particuliers telles que les étoiles orientées et les chaînes en élaborant, pour les cas polynomiaux, différents algorithmes reposant principalement sur la programmation dynamique et l'utilisation de relaxations lagrangiennes. Nous généralisons ensuite cette approche en considérant les versions multicritères des problèmes de coupes et de multicoupes. Nous prouvons que ces derniers sont NP-complets même dans des topologies très simples comme les chaînes ou les cycles. Dans la seconde partie de ce mémoire, nous abordons des problèmes de recherche de sous-graphes induits. Nous nous intéressons principalement à la recherche d'arbres, de chaînes et de cycles induits couvrant un ensemble T de sommets donnés. Après avoir prouvé la NP-complétude des cas généraux, nous nous focalisons davantage sur les cas où la cardinalité de T est fixée. Nous donnons également plusieurs résultats structurels pour les graphes de maille suffisamment large.
|
2 |
Detecting and Coloring some Graph Classes / Détection et coloration de certaines classes de graphesLe, Ngoc Khang 08 June 2018 (has links)
Les graphes sont des structures mathématiques utilisées pour modéliser les relations par paires entre objets. Malgré leur structure simple, les graphes ont des applications dans divers domaines tels que l'informatique, la physique, la biologie et la sociologie. L'objectif principal de ce travail est de continuer l'étude des problèmes de coloration et de détection dans le cadre de classes de graphes fermées par sous-graphes induits (que nous appelons classes de graphes héréditaires).La première classe que nous considérons est graphes sans ISK4 - les graphes qui ne contiennent aucune subdivision de en tant que sous-graphe induit. Nous montrons que le nombre chromatique de cette classe est limité à 24, une amélioration considérable par rapport à la borne existant précédemment. Nous donnons également une bien meilleure limite dans le cas sans triangle. De plus, nous prouvons qu'il existe un algorithme de complexité pour détecter cette classe, ce qui répond à une question de Chudnovsky et al. et Lévêque et al.La deuxième classe que nous étudions est celle des graphes sans trou pair et sans étoile d’articulation. Cela est motivé par l'utilisation de la technique de décomposition pour résoudre certains problèmes d'optimisation. Nous garantissons la fonction χ-bounding optimale pour cette classe. Nous montrons que la classe a rank-width bornée, ce qui implique l'existence d'un algorithme de coloration en temps polynomial. Enfin, la coloration gloutonne connexe dans les graphes sans griffes est considérée. Une façon naturelle de colorier un graphe est d'avoir un ordre de ses sommets et d'affecter pour chaque sommet la première couleur disponible. Beaucoup de recherches ont été faites pour des ordres généraux. Cependant, nous connaissons très peu de choses sur la caractérisation des bons graphes par rapport aux ordres connexes. Un graphe est bon si pour chaque sous-graphe induit connexe de , chaque ordre connexe donne à une coloration optimale. Nous donnons la caractérisation complète de bons graphes sans griffes en termes de sous-graphes induits minimaux interdits. / Graphs are mathematical structures used to model pairwise relations between objects. Despite their simple structures, graphs have applications in various areas like computer science, physics, biology and sociology. The main focus of this work is to continue the study of the coloring and detecting problems in the setting of graph classes closed under taking induced subgraphs (which we call hereditary graph classes). The first class we consider is ISK4-free graphs - the graphs that do not contain any subdivision of K4 as an induced subgraph. We prove that the chromatic number of this class is bounded by 24, a huge improvement compared to the best-known bound. We also give a much better bound in the triangle-free case. Furthermore, we prove that there exists an O(n 9) algorithm for detecting this class, which answers a question by Chudnovsky et al. and Lévêque et al. The second class we study is even-hole-free graphs with no star cutset. This was motivated by the use of decomposition technique in solving some optimization problems. We prove the optimal χ -bounding function for this class and show that it has bounded rank-width, which implies the existence of a polynomial-time coloring algorithm.Finally, the connected greedy coloring in claw-free graphs is considered. A natural way to color a graph is to have an order of its vertices and assign for each vertex the first available color. A lot of researches have been done for general orders. However, we know very little about the characterization of good graphs with respect to connected orders. A graph G is good if for every connected induced subgraph H of G, every connected order gives H an optimal coloring. We give the complete characterization of good claw-free graphs in terms of minimal forbidden induced subgraphs.
|
Page generated in 0.0382 seconds