Upper bounds to the clique width of graphs

Upper bounds to the clique width of graphs

0.00 Avg rating0 Votes
Article ID: iaor20013540
Country: Netherlands
Volume: 101
Issue: 1/3
Start Page Number: 77
End Page Number: 114
Publication Date: Apr 2000
Journal: Discrete Applied Mathematics
Authors: ,
Abstract:

Hierarchical decompositions of graphs are interesting for algorithmic purposes. Many NP complete problems have linear complexity on graphs with tree-decompositions of bounded width. We investigate alternate hierarchical decompositions that apply to wider classes of graphs and still enjoy good algorithmic properties. These decompositions are motivated and inspired by the study of vertex-replacement context-free graph grammars. The complexity measure of graphs associated with these decompositions is called clique width. In this paper we bound the clique width of a graph in terms of its tree width on the one hand, and of the clique width of its edge complement on the other.

Reviews

Required fields are marked *. Your email address will not be published.