Décompositions de graphes : quelques limites et obstructions
Les décompositions de graphes, lorsqu elles sont de petite largeur, sont souvent utilisées pour résoudre plus efficacement des problèmes étant difficiles dans le cas de graphes quelconques. Dans ce travail de thèse, nous nous intéressons aux limites liées à ces décompositions, et à la construction d...
Kaydedildi:
| Yazar: | |
|---|---|
| Diğer Yazarlar: | |
| Materyal Türü: | Thèse numérique |
| Dil: | Français |
| Baskı/Yayın Bilgisi: |
2011.
|
| Konular: | |
| Online Erişim: | Accès au texte intégral https://theses.univ-orleans.fr/public/2011ORLE2057_va.pdf http://www.theses.fr/2011ORLE2057/abes |
| Not: |
Titre provenant de l'écran-titre Ecole(s) Doctorale(s) : École doctorale Sciences et technologies (Orléans ; 2009-2012) Partenaire(s) de recherche : Laboratoire d'informatique fondamentale d'Orléans (Orléans ; 1987-....) (Laboratoire) Autre(s) contribution(s) : Michel Habib (Président du jury) ; Ioan Todinca, Michel Habib, Cyril Gavoille, Yann Vaxès, Mathieu Liedloff (Membre(s) du jury) ; Cyril Gavoille, Christophe Paul (Rapporteur(s)) |
| Autres localisations: | Voir dans le Sudoc |
| Variante du titre: | Graphs decompositions :, some limits and obstructions |
| LEADER | 04682nam a22003737a 4500 | ||
|---|---|---|---|
| 001 | 418804 | ||
| 008 | 120516s2011 xxe ||| |||| 00| 0 fre d | ||
| 009 | PPN161099955 | ||
| 041 | 0 | |a fre |b fre |b eng | |
| 084 | |a 004 | ||
| 100 | 1 | |a Chapelle, Mathieu, |d 1983- . | |
| 240 | 1 | 0 | |a Graphs decompositions : |b some limits and obstructions |
| 245 | 1 | 0 | |a Décompositions de graphes : |b quelques limites et obstructions |c Mathieu Chapelle ; sous la direction de Ioan Todinca. |
| 256 | |a Données textuelles | ||
| 260 | |c 2011. | ||
| 500 | |a Titre provenant de l'écran-titre | ||
| 500 | |a Ecole(s) Doctorale(s) : École doctorale Sciences et technologies (Orléans ; 2009-2012) | ||
| 500 | |a Partenaire(s) de recherche : Laboratoire d'informatique fondamentale d'Orléans (Orléans ; 1987-....) (Laboratoire) | ||
| 500 | |a Autre(s) contribution(s) : Michel Habib (Président du jury) ; Ioan Todinca, Michel Habib, Cyril Gavoille, Yann Vaxès, Mathieu Liedloff (Membre(s) du jury) ; Cyril Gavoille, Christophe Paul (Rapporteur(s)) | ||
| 502 | |a Thèse de doctorat. Informatique. Orléans. 2011 | ||
| 520 | |a Les décompositions de graphes, lorsqu elles sont de petite largeur, sont souvent utilisées pour résoudre plus efficacement des problèmes étant difficiles dans le cas de graphes quelconques. Dans ce travail de thèse, nous nous intéressons aux limites liées à ces décompositions, et à la construction d obstructions certifiant leur grande largeur. Dans une première partie, nous donnons un algorithme généralisant et unifiant la construction d obstructions pour différentes largeurs de graphes, en temps XP lorsque paramétré par la largeur considérée. Nous obtenons en particulier le premier algorithme permettant de construire efficacement une obstruction à la largeur arborescente en temps O(ntw+4). La seconde partie de notre travail porte sur l étude du problème ENSEMBLE [ , ]-DOMINANT, une généralisation des problèmes de domination sur les graphes et caractérisée par deux ensembles d entiers et . Les diverses études de ce problème apparaissant dans la littérature concernent uniquement les cas ou le problème est FPT, lorsque paramétré par la largeur arborescente. Nous montrons que ce problème ne l est pas toujours, et que pour certains cas d ensembles et , il devient W[1]-difficile lorsque paramétré par la largeur arborescente. Dans la dernière partie, nous étudions la complexité d un nouveau problème de coloration appelé k-COLORATION ADDITIVE, combinant théorie des graphes et théorie des nombres. Nous montrons que ce nouveau problème est NP-complet pour tout k >= 4 fixé, tandis qu il peut être résolu en temps polynomial sur les arbres pour k quelconque et non fixé. | ||
| 520 | |a Graphs decompositions of small width are usually used to solve efficiently problems which are difficult in general. In this thesis, we focus on some limits of these decompositions, and the construction of some obstructions certifying a large width. First, we give a generic algorithm unifying obstructions construction for several graph widths, in XP time when parameterized by the considered width. In particular, it gives the first algorithm computing efficiently an obstruction to tree-width in time O(ntw+4). Secondly, we study the parameterized complexity of [ , ]-DOMINATING SET, a generalization of some domination problems characterized by two sets of integers and . All known studies focused only on cases where this problem is FPT when parameterized by tree-width. In this work, we show that there are some cases where the problem is no longer FPT, and become W[1]-hard instead. Finally, we study the computational complexity of a new coloration problem, named k-ADDITIVE COLORING, which combines both graph theory and number theory. We show that this new problem is NP-complete for any fixed number k >= 4, while it can be solved in polynomial time on trees for any k. | ||
| 538 | |a Configuration requise : un logiciel capable de lire un fichier au format : PDF | ||
| 650 | |a Théorie des graphes | ||
| 650 | |a Théorie des obstructions | ||
| 650 | |a Problèmes aux limites | ||
| 650 | |a Coloriage de graphes | ||
| 650 | |a Thèses et écrits académiques | ||
| 700 | 1 | |a Todinca, Ioan, |d 19..- |4 ths |4 opn | |
| 710 | 2 | |a Université d'Orléans. |4 dgg | |
| 856 | 4 | |q PDF |s 1852014 |u http://www.theses.fr/2011ORLE2057/document |z Accès au texte intégral | |
| 856 | 4 | |u https://theses.univ-orleans.fr/public/2011ORLE2057_va.pdf | |
| 856 | 4 | |u http://www.theses.fr/2011ORLE2057/abes | |
| 997 | |0 418804 |1 Thèse numérique |a Ressource numérique |b INSA |b ENSA |c 0/Bibliothèque numérique/ |c 1/Bibliothèque numérique/Autre ressource numérique/ | ||