Décompositions de graphes et algorithmes efficaces - Université de Lorraine Accéder directement au contenu
Thèse Année : 2006

Décompositions de graphes et algorithmes efficaces

Michaël Rao

Résumé

This thesis deals with the modular decomposition and several of its generalizations. In a first time we show how graph decompositions can be used to solve efficiently some problems on graphs. We show how the modular decomposition can be used to obtain linear algorithms for " independent set ", " clique ", " chromatic number " and " partition into cliques " on (P_5,gem)-free graphs. We also show how the split decomposition can be used to compute the chromatic number, and we give a new class of vertex partitioning problems which can be solved in polynomial time on graphs of bounded clique width. In a second time, we are interested to generalize the modular decomposition. We study a new decomposition called the bi-join decomposition. We give in particular several characterizations of completely decomposable graphs, and a linear time decomposition algorithm. We introduce some parametrized generalization of the modular decomposition, and we show that theses generalizations are relatively close to the clique width.
Ce mémoire traite de la décomposition modulaire ainsi que différentes de ses généralisations. Dans un premier temps, on explique comment se servir de décompositions pour résoudre efficacement certains problèmes sur les graphes. En particulier, en utilisant la décomposition modulaire, on obtient des algorithmes linéaires pour les problèmes " ensemble stable ", " clique ", " nombre chromatique " et " partition en cliques " sur les graphes sans P_5 et gem induit. On étudie également comment la décomposition en coupes peut servir pour calculer le nombre chromatique, et on exhibe une nouvelle classe de problèmes de partitionnements pour lesquels on peut obtenir des algorithmes polynomiaux sur les graphes de largeur de clique bornée. Dans un second temps, on s'intéresse à généraliser la décomposition modulaire. On étudiera une nouvelle décomposition appelée décomposition bi-joint. On donne notamment différentes caractérisations des graphes complètement décomposables par cette décomposition, et un algorithme linéaire pour la calculer. On donne également des généralisations paramétrées de la décomposition modulaire, qui s'avèrent relativement proches de la largeur de clique.
Fichier principal
Vignette du fichier
Rao.Michael.SMZ0607.pdf (1.48 Mo) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

tel-01752468 , version 1 (29-03-2018)

Identifiants

  • HAL Id : tel-01752468 , version 1

Citer

Michaël Rao. Décompositions de graphes et algorithmes efficaces. Autre [cs.OH]. Université Paul Verlaine - Metz, 2006. Français. ⟨NNT : 2006METZ007S⟩. ⟨tel-01752468⟩
149 Consultations
158 Téléchargements

Partager

Gmail Facebook X LinkedIn More