Skip to Main content Skip to Navigation
Journal articles

Solving Some NP-Complete Problems using Split Decomposition

Michaël Rao 1
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : We show how to use the split decomposition to solve some NP-hard optimization problems on graphs. We give algorithms for clique problem and domination-type problems. Our main result is an algorithm to compute a coloration of a graph using its split decomposition. Finally we show that the clique-width of a graph is bounded if and only if the clique-width of each representative graph in its split decomposition is bounded.
Document type :
Journal articles
Complete list of metadata
Contributor : Michael Rao Connect in order to contact the contributor
Submitted on : Thursday, September 25, 2008 - 1:42:13 PM
Last modification on : Monday, October 11, 2021 - 1:24:06 PM

Links full text




Michaël Rao. Solving Some NP-Complete Problems using Split Decomposition. Discrete Applied Mathematics, Elsevier, 2008, 156 (14), pp.2768-2780. ⟨10.1016/j.dam.2007.11.013⟩. ⟨lirmm-00324549⟩



Record views