Sur quelques généralisations polynomiales de la décomposition modulaire

La decomposition modulaire est une decomposition de graphes tres etudiee depuis son introduction en 67 par Gallai. Cette decomposition s'est montree etre un outils tres puissant tant d'un point de vue theorique que d'un point de vue algorithmique. Dans cette these nous abordons ces deux aspects. Nous proposons deux generalisations de la decomposition modulaire et nous systematisons l'usage d'une technique tres connue en algorithmique, l'affinage de partitions, pour resoudre les problemes souleves par ces generalisations. Le memoire se divise en deux parties, la premiere partie est consacree a l'introduction et l'etude de deux generalisations de la decomposition modulaire. Pour ce faire, nous introduisons une nouvelle structure discrete: les "relations homogenes" qui abstrait la notion de voisinage pour ne retenir que la notion essentielle de distinction. Nous etudions les proprietes comminatoires de la decomposition modulaire sur cette structure et nous presentons des methodes pour calculer cette decomposition efficacement. Ensuite, nous introduisons une nouvelle decomposition, la decomposition en "umodules". H s'agit d'adopter le point de vue dual de la decomposition modulaire. La seconde partie presente des algorithmes efficaces pour resoudre les deux problemes suivants. Le premier probleme consiste a trouver les composantes de chevauchement d'une famille de partie d'un ensemble fini. Nous presentons un algorithme du a Dahlhaus et simplifions ce dernier en remplacant une procedure complexe par une technique d'affinage de partition. Le second algorithme reconnait les graphes de largeur Nlc-2 en temps S0(n ^2m)S et fournit une methode de meme complexite pour resoudre le probleme de l'isomorphisme sur cette classe.