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.
Type de document :
Article dans une revue
Discrete Applied Mathematics, Elsevier, 2008, 156 (14), pp.2768-2780. 〈10.1016/j.dam.2007.11.013〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00324549
Contributeur : Michael Rao <>
Soumis le : jeudi 25 septembre 2008 - 13:42:13
Dernière modification le : jeudi 24 mai 2018 - 15:59:22

Lien texte intégral

Identifiants

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〉

Partager

Métriques

Consultations de la notice

153