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 · date | New search

You searched for subject:(Sous graphes induits). Showing records 1 – 3 of 3 total matches.

Search Limiters

Last 2 Years | English Only

No search limiters apply to these results.

▼ Search Limiters


Université du Québec à Montréal

1. Abdenbi, Moussa. Sous-arbres induits dans les graphes séries-parallèles.

Degree: 2019, Université du Québec à Montréal

Dans ce mémoire nous nous intéressons au problème qui, étant donné un graphe simple G, interroge l'existence de sous-arbres induits de taille i ayant le plus grand nombre de feuilles. Un tel sous-arbre induit s'il existe est dit pleinement feuillu. Ce problème d'optimisation que nous nommons SAIPF pour sous-arbres induits pleinement feuillus, est associé au problème de décision SAIF, pour sous-arbres induits feuillus, que nous pouvons énoncer ainsi : étant donné un graphe simple G et deux entiers positifs i et f, est-ce qu'il existe un sous-arbre induit dans G avec i sommets et f, feuilles? Nous démontrons que ce problème est NP-complet dans le cas général, ce qui fait du problème SAIPF un problème NP-difficile. Ces problèmes n'étant probablement pas résolubles avec des algorithmes en temps polynomial, comme alternative, nous nous intéressons plutôt à des familles de graphes spécifiques où de tels algorithmes ont plus de chance d'exister. Nous considérons donc une sous-famille de graphes planaires, la famille particulière des graphes séries-parallèles, où le problème est "facile". Cette famille est définie récursivement par une succession de compositions en série ou en parallèle. Cette définition qui nous a permis, entre autres, de suivre la construction d'un graphe série-parallèle, nous a aussi permis d'énoncer un résultat essentiel de préservation d'optimalité dans ce processus de construction. Résultat qui a motivé et a inspiré la formulation d'équations récursives qui couvrent tous les cas possibles de construction de sous-arbres induits pleinement feuillus. Il s'avère que ces équations cachent des algorithmes de complexité temporelle polynomiale. Nous avons donc traduit ces équations en algorithmes qui prennent en paramètre d 'entrée la représentation arborescente d 'un graphe série-parallèle, appelée arbre de construction, et qui fournissent en sortie le nombre maximal de feuilles qu'un sous-arbre induit, s'il existe, peut réaliser pour un nombre de sommets donné. _____________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : Graphe série-parallèle, sous-arbre induit, feuille, pleinement feuillu, arbre de construction, graphe planaire

Subjects/Keywords: Théorie des graphes; Arbres; Sous-graphes induits; Graphes séries-parallèles; Algorithmes

Record DetailsSimilar RecordsGoogle PlusoneFacebookTwitterCiteULikeMendeleyreddit

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

APA (6th Edition):

Abdenbi, M. (2019). Sous-arbres induits dans les graphes séries-parallèles. (Thesis). Université du Québec à Montréal. Retrieved from http://archipel.uqam.ca/12833/1/M16054.pdf

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Chicago Manual of Style (16th Edition):

Abdenbi, Moussa. “Sous-arbres induits dans les graphes séries-parallèles.” 2019. Thesis, Université du Québec à Montréal. Accessed February 25, 2021. http://archipel.uqam.ca/12833/1/M16054.pdf.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

MLA Handbook (7th Edition):

Abdenbi, Moussa. “Sous-arbres induits dans les graphes séries-parallèles.” 2019. Web. 25 Feb 2021.

Vancouver:

Abdenbi M. Sous-arbres induits dans les graphes séries-parallèles. [Internet] [Thesis]. Université du Québec à Montréal; 2019. [cited 2021 Feb 25]. Available from: http://archipel.uqam.ca/12833/1/M16054.pdf.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Council of Science Editors:

Abdenbi M. Sous-arbres induits dans les graphes séries-parallèles. [Thesis]. Université du Québec à Montréal; 2019. Available from: http://archipel.uqam.ca/12833/1/M16054.pdf

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

2. 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 February 25, 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. 25 Feb 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 Feb 25]. 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


Université du Québec à Montréal

3. Nadeau, Émile. Sous-arbres induits pleinement feuillus.

Degree: 2018, Université du Québec à Montréal

L'étude des sous-arbres induits pleinement feuillus est un nouveau sujet d'intérêt en théorie des graphes. Un sous-graphe induit est un sous-graphe constitué d'un ensemble de sommets et de toutes les arêtes qui les relient. Un sous-graphe induit qui est un arbre est appelé sous-arbre induit. On dit, de plus, qu'il est pleinement feuillu, s'il maximise son nombre de feuilles parmi tous les sous-arbres induits de même taille dans le graphe. L'objectif de ce travail est d'étudier ces objets d'un point de vue algorithmique et de tenter de les caractériser. Dans un premier temps, on introduit la fonction feuille d'un graphe qui à chaque entier n, associe le nombre maximal de feuilles qu'un sous-arbre induit de taille n peut réaliser, c'est-à-dire le nombre de feuilles d'un sous-arbre induit pleinement feuillu de taille n. On montre que le calcul de la fonction feuille est un problème difficile, puis on introduit une structure de données que l'on utilise dans un algorithme de type séparation et évaluation progressive, pour le calcul de la fonction feuille. La démonstration de l'exactitude de l'algorithme est présentée et des données empiriques sur sa performance sont analysées. Dans un deuxième temps, on introduit le problème de réalisation de la fonction feuille, qui consiste à décider si une fonction donnée est la fonction feuille d'un certain graphe. On utilise des outils de la combinatoire des mots pour donner des conditions nécessaires afin qu'une fonction soit réalisable. On présente, ensuite, un outil supplémentaire, les mots préfixes normaux. Ces derniers se définissent ainsi : il s'agit des mots binaires dont chaque préfixe contient plus de 1 que tous les facteurs de la même longueur que ce préfixe. Finalement, à l'aide de cet ensemble de mots, on décrit les fonctions feuilles qui peuvent être réalisées par un graphe chenille et on donne une caractérisation des graphes chenilles ayant la même fonction feuille. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : Théorie des graphes, arbres, NP-complet, chenilles, graphes induits

Subjects/Keywords: Théorie des graphes; Arbres; Problèmes NP-complets; Graphes chenilles; Sous-graphes induits; Sous-arbre induit pleinement feuillu

Record DetailsSimilar RecordsGoogle PlusoneFacebookTwitterCiteULikeMendeleyreddit

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

APA (6th Edition):

Nadeau, . (2018). Sous-arbres induits pleinement feuillus. (Thesis). Université du Québec à Montréal. Retrieved from http://archipel.uqam.ca/12310/1/M15895.pdf

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Chicago Manual of Style (16th Edition):

Nadeau, Émile. “Sous-arbres induits pleinement feuillus.” 2018. Thesis, Université du Québec à Montréal. Accessed February 25, 2021. http://archipel.uqam.ca/12310/1/M15895.pdf.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

MLA Handbook (7th Edition):

Nadeau, Émile. “Sous-arbres induits pleinement feuillus.” 2018. Web. 25 Feb 2021.

Vancouver:

Nadeau . Sous-arbres induits pleinement feuillus. [Internet] [Thesis]. Université du Québec à Montréal; 2018. [cited 2021 Feb 25]. Available from: http://archipel.uqam.ca/12310/1/M15895.pdf.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Council of Science Editors:

Nadeau . Sous-arbres induits pleinement feuillus. [Thesis]. Université du Québec à Montréal; 2018. Available from: http://archipel.uqam.ca/12310/1/M15895.pdf

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

.