Solving some NP-complete problems using split decomposition

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-widt...

Full description

Saved in:
Bibliographic Details
Published in:Discrete Applied Mathematics 2008-07, Vol.156 (14), p.2768-2780
Main Author: Rao, Michaël
Format: Article
Language:English
Subjects:
Algorithmics. Computability. Computer arithmetics
Applied sciences
Calculus of variations and optimal control
Clique-width
Combinatorics
Combinatorics. Ordered structures
Computer Science
Computer science
control theory
systems
Discrete Mathematics
Exact sciences and technology
Graph algorithms
Graph coloring
Graph theory
Mathematical analysis
Mathematics
NP-complete problems
Numerical analysis
Numerical analysis. Scientific computation
Numerical methods in mathematical programming, optimization and calculus of variations
Sciences and techniques of general use
Split decomposition
Theoretical computing
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0166-218X
1872-6771
DOI:10.1016/j.dam.2007.11.013