Solving some NP-complete problems using split decomposition |
| |
Authors: | Michaël Rao |
| |
Institution: | aCNRS - LIRMM, Université Montpellier II, 161 rue Ada, 34392 Montpellier Cedex 5, France |
| |
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. |
| |
Keywords: | Graph algorithms Graph coloring NP-complete problems Split decomposition Clique-width |
本文献已被 ScienceDirect 等数据库收录! |