Etude de différents problèmes de partition de graphes
Thèses de doctorat
Fecha de defensa
2006-11-17Resumen
Dans ce mémoire, on s'intéresse à différentes notions de partition de graphes telles que l'arboricité ou la planarité externe. On se concentre sur la famille des graphes planaires. On montre notamment que tout graphe ...Leer más >
Dans ce mémoire, on s'intéresse à différentes notions de partition de graphes telles que l'arboricité ou la planarité externe. On se concentre sur la famille des graphes planaires. On montre notamment que tout graphe planaire est l'union de : - deux graphes planaires externes - quatre forêts de chenilles - trois forêts dont une est de degré maximum au plus quatre. On donne également quelques résultats de complexité concernant des problèmes de décision liés à différents types d'arboricités. On définit enfin de nouvelles notions d'arboricité telles que l'arboricité mixte ou l'arboricité circulaire.< Leer menos
Palabras clave
Informatique
théorie des graphes
graphes planaires
partitionnement
graphes planaires externes
arboricité
Centros de investigación