Abstract FR:

Partant de travaux sur la structure des graphes premiers (ou indecomposables), nous presentons dans le cas des graphes non-orientes un algorithme de reconnaissance des graphes premiers (complexite de l'ordre de o(n+m log n)). Nous en deduisons en utilisant les proprietes d'une classe particuliere de graphes (les cographes) un algorithme de decomposition par substitution des graphes non orientes (complexite quadratique). Ce travail est ensuite generalise aux deux cas des graphes orientes et des graphes etiquetes