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 metadatas

https://hal.univ-lorraine.fr/tel-01752468
Contributor : Thèses Ul <>
Submitted on : Thursday, March 29, 2018 - 1:48:54 PM
Last modification on : Friday, January 25, 2019 - 3:42:09 PM

File

Rao.Michael.SMZ0607.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : tel-01752468, version 1

Collections

Citation

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

Share

Metrics

Record views

39

Files downloads

40