Solving Some NP-Complete Problems using Split Decomposition - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Journal Articles Discrete Applied Mathematics Year : 2008

Solving Some NP-Complete Problems using Split Decomposition

Michaël Rao

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.

Dates and versions

lirmm-00324549 , version 1 (25-09-2008)

Identifiers

Cite

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

Altmetric

Share

Gmail Mastodon Facebook X LinkedIn More