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 metadatas

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00324549
Contributor : Michael Rao <>
Submitted on : Thursday, September 25, 2008 - 1:42:13 PM
Last modification on : Thursday, February 7, 2019 - 2:52:51 PM

Links full text

Identifiers

Collections

Citation

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⟩

Share

Metrics

Record views

184