On the Relationship Between Clique-Width and Treewidth
On the Relationship Between Clique-Width and Treewidth
复制标题
论团宽度与树宽度的关系
DOI：
--
复制
发表时间：
2001
期刊：
影响因子：
--
通讯作者：
Udi Rotics
中科院分区：
文献类型：
--
作者：
D. Corneil;Udi Rotics
树宽通常被认为是图结构的最有用的参数化之一。团宽度是一种类似的参数化，它共享树宽的一个强大性质，即：如果一个图具有有界树宽(或团宽度)，则对于任何可用一元二阶逻辑表示的图问题，都有一个多项式时间算法，使用顶点上的量词(在团宽度的情况下，您必须假设给出了团宽度解析表达式)。Courcelle和Olariu在研究树宽与团宽之间的关系时，证明了任何有界树宽的图也是有界团宽的，特别是对于树宽为k的图G，其团宽为G？4*2k-1+1。本文将这一结果推广到G？3*2k-1的团宽，更重要的是证明了这种关系存在一个指数下界。特别地，对于任意k，存在一个树宽=k的图G，其中G？2？k/2？-1的团宽度.
Treewidth is generally regarded as one of the most useful parameterizations of a graph's construction. Clique-width is a similar parameterizations that shares one of the powerful properties of treewidth, namely: if a graph is of bounded treewidth (or clique-width), then there is a polynomial time algorithm for any graph problem expressible in Monadic Second Order Logic, using quantifiers on vertices (in the case of clique-width you must assume a clique-width parse expression is given). In studying the relationship between treewidth and clique-width, Courcelle and Olariu showed that any graph of bounded treewidth is also of bounded clique-width; in particular, for any graph G with treewidth k, the clique-width of G ? 4 * 2k-1 + 1.In this paper, we improve this result to the clique-width of G ? 3 * 2k-1 and more importantly show that there is an exponential lower bound on this relationship. In particular, for any k, there is a graph G with treewidth = k where the clique-width of G ? 2?k/2?-1.