Advanced search options

Advanced Search Options 🞨

Browse by author name (“Author name starts with…”).

Find ETDs with:

in
/  
in
/  
in
/  
in

Written in Published in Earliest date Latest date

Sorted by

Results per page:

Sorted by: relevance · author · university · dateNew search

You searched for +publisher:"Lyon" +contributor:("Trotignon, Nicolas"). Showing records 1 – 2 of 2 total matches.

Search Limiters

Last 2 Years | English Only

No search limiters apply to these results.

▼ Search Limiters

1. Le, Ngoc Khang. Detecting and Coloring some Graph Classes : Détection et coloration de certaines classes de graphes.

Degree: Docteur es, Informatique, 2018, Lyon

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…

Advisors/Committee Members: Trotignon, Nicolas (thesis director).

Subjects/Keywords: Coloration de graphe; Reconnaissance de graphe; Sous-graphes induits; Graphes sans ISK4; Graphes sans trou pair; Coloration gloutonne connexe; Graph coloring; Graph recognition; Induced subgraphs; ISK4-free graphs; Even-hole-free graphs; Connected greedy coloring

Record DetailsSimilar RecordsGoogle PlusoneFacebookTwitterCiteULikeMendeleyreddit

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6th Edition):

Le, N. K. (2018). Detecting and Coloring some Graph Classes : Détection et coloration de certaines classes de graphes. (Doctoral Dissertation). Lyon. Retrieved from http://www.theses.fr/2018LYSEN021

Chicago Manual of Style (16th Edition):

Le, Ngoc Khang. “Detecting and Coloring some Graph Classes : Détection et coloration de certaines classes de graphes.” 2018. Doctoral Dissertation, Lyon. Accessed January 19, 2021. http://www.theses.fr/2018LYSEN021.

MLA Handbook (7th Edition):

Le, Ngoc Khang. “Detecting and Coloring some Graph Classes : Détection et coloration de certaines classes de graphes.” 2018. Web. 19 Jan 2021.

Vancouver:

Le NK. Detecting and Coloring some Graph Classes : Détection et coloration de certaines classes de graphes. [Internet] [Doctoral dissertation]. Lyon; 2018. [cited 2021 Jan 19]. Available from: http://www.theses.fr/2018LYSEN021.

Council of Science Editors:

Le NK. Detecting and Coloring some Graph Classes : Détection et coloration de certaines classes de graphes. [Doctoral Dissertation]. Lyon; 2018. Available from: http://www.theses.fr/2018LYSEN021

2. Trunck, Théophile. Trigraphes de Berge apprivoisés : Tame Berge trigraphes.

Degree: Docteur es, Informatique, 2014, Lyon, École normale supérieure

L'objectif de cette thèse est de réussir à utiliser des décompositions de graphes afin de résoudre des problèmes algorithmiques sur les graphes. Notre objet d'étude principal est la classe des graphes de Berge apprivoisés. Les graphes de Berge sont les graphes ne possédant ni cycle de longueur impaire supérieur à 4 ni complémentaire de cycle de longueur impaire supérieure à 4. Dans les années 60, Claude Berge a conjecturé que les graphes de Berge étaient des graphes parfaits. C'est-à-dire que la taille de la plus grande clique est exactement le nombre minimum de couleurs nécessaire à une coloration propre et ce pour tout sous-graphe. En 2002, Chudnovsky, Robertson, Seymour et Thomas ont démontré cette conjecture en utilisant un théorème de structure: les graphes de Berge sont basiques ou admettent une décomposition. Ce résultat est très utile pour faire des preuves par induction. Cependant, une des décompositions du théorème, la skew-partition équilibrée, est très difficile à utiliser algorithmiquement. Nous nous focalisons donc sur les graphes de Berge apprivoisés, c'est-à-dire les graphes de Berge sans skew-partition équilibrée. Pour pouvoir faire des inductions, nous devons adapter le théorème destructure de Chudnovsky et al à notre classe. Nous prouvons un résultat plus fort: les graphes de Berge apprivoisés sont basiques ou admettent une décomposition telle qu'un côté de la décomposition soit toujours basique. Nous avons de plus un algorithme calculant cette décomposition. Nous utilisons ensuite notre théorème pour montrer que les graphes de Berge apprivoisés admettent la propriété du grand biparti, de la clique-stable séparation et qu'il existe un algorithme polynomial permettant de calculer le stable maximum.

The goal of this these is to use graph's decompositions to solve algorithmic problems on graphs. We will study the class of Berge tame graphs. A Berge graph is a graph without cycle of odd length at least 4 nor complement of cycle of odd length at least 4.In the 60's, Claude Berge conjectured that Berge graphs are perfect graphs. The size of the biggest clique is exactly the number of colors required to color the graph. In 2002, Chudnovsky, Robertson, Seymour et Thomas proved this conjecture using a theorem of decomposition: Berge graphs are either basic or have a decomposition. This is a useful result to do proof by induction. Unfortunately, one of the decomposition, the skew-partition, is really hard to use. We arefocusing here on Berge tame graphs, i.e~Berge graph without balanced skew-partition. To be able to do induction, we must first adapt the Chudnovsky et al's theorem of structure to our class. We prove a stronger result: Berge tame graphs are basic or have a decomposition such that one side is always basic. We also have an algorithm to compute this decomposition. We then use our theorem to prouve that Berge tame graphs have the big-bipartite property, the clique-stable set separation property and there exists a polytime algorithm to compute the maximum stable set.

Advisors/Committee Members: Trotignon, Nicolas (thesis director).

Subjects/Keywords: Graphes parfaits; 2-joint; Clique-stable séparation; Décompositions extrêmes; Perfect graphs; 2-join; Clique-stable separator; Extreme decompositions

Record DetailsSimilar RecordsGoogle PlusoneFacebookTwitterCiteULikeMendeleyreddit

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6th Edition):

Trunck, T. (2014). Trigraphes de Berge apprivoisés : Tame Berge trigraphes. (Doctoral Dissertation). Lyon, École normale supérieure. Retrieved from http://www.theses.fr/2014ENSL0929

Chicago Manual of Style (16th Edition):

Trunck, Théophile. “Trigraphes de Berge apprivoisés : Tame Berge trigraphes.” 2014. Doctoral Dissertation, Lyon, École normale supérieure. Accessed January 19, 2021. http://www.theses.fr/2014ENSL0929.

MLA Handbook (7th Edition):

Trunck, Théophile. “Trigraphes de Berge apprivoisés : Tame Berge trigraphes.” 2014. Web. 19 Jan 2021.

Vancouver:

Trunck T. Trigraphes de Berge apprivoisés : Tame Berge trigraphes. [Internet] [Doctoral dissertation]. Lyon, École normale supérieure; 2014. [cited 2021 Jan 19]. Available from: http://www.theses.fr/2014ENSL0929.

Council of Science Editors:

Trunck T. Trigraphes de Berge apprivoisés : Tame Berge trigraphes. [Doctoral Dissertation]. Lyon, École normale supérieure; 2014. Available from: http://www.theses.fr/2014ENSL0929

.