Upper bounds to the clique width of graphs
Upper bounds to the clique width of graphs
复制标题
DOI：
10.1016/s0166-218x(99)00184-5
复制
发表时间：
2000-04-15
影响因子：
1.1
通讯作者：
Olariu, S
中科院分区：
文献类型：
--
作者：
Courcelle, B;Olariu, S
图的分层分解对于算法目的很有趣。许多 NP 完全问题在具有有界宽度的树分解的图上具有线性复杂性。我们研究了适用于更广泛的图类的替代层次分解，并且仍然具有良好的算法特性。这些分解的动机和灵感来自于顶点替换上下文无关图语法的研究。与这些分解相关的图的复杂性度量称为团宽度。在本文中，我们一方面根据图的树宽度来限制图的团宽度，另一方面根据图的边补集的团宽度来限制图的团宽度。 (C) 2000 Elsevier Science B.V. 保留所有权利。
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. (C) 2000 Elsevier Science B.V. All rights reserved.