| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 420766 | Discrete Applied Mathematics | 2008 | 13 Pages |
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Michaël Rao,