Skip to Main content Skip to Navigation

Décompositions de graphes et algorithmes efficaces

Abstract : 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.
Complete list of metadata
Contributor : Thèses UL Connect in order to contact the contributor
Submitted on : Thursday, March 29, 2018 - 1:48:54 PM
Last modification on : Friday, January 25, 2019 - 3:42:09 PM


Files produced by the author(s)


  • HAL Id : tel-01752468, version 1



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



Record views


Files downloads