On the Band-, Tree-, and Clique-Width of Graphs with Bounded Vertex Degree
On the Band-, Tree-, and Clique-Width of Graphs with Bounded Vertex Degree
复制标题
关于有界顶点度图的带宽、树宽和团宽
DOI：
--
复制
发表时间：
2004
影响因子：
0.8
通讯作者：
D. Rautenbach
中科院分区：
文献类型：
--
作者：
V. Lozin;D. Rautenbach
由于许多限制到这些参数之一是图形，因此可以在多项式时间内求解，因此可以在多项式时间内求解许多np-hard的问题，因此算法图理论中的带，树和集团宽度在算法图中至关重要。有限。众所周知，对于任何固定的$ delta geq 3 $，所有三个参数均无限于最多$ delta $的顶点学位的图形。在本文中，我们区分具有有界的顶点度的图形的代表性子类，具有有界的带，树或集团的宽度。我们的证明是建设性的，并导致有效的算法在限制在这些类别的情况下时，用于各种NP螺旋图问题。
The band-, tree-, and clique-width are of primary importance in algorithmic graph theory due to the fact that many problems that are NP-hard for general graphs can be solved in polynomial time when restricted to graphs where one of these parameters is bounded. It is known that for any fixed $Delta geq 3$, all three parameters are unbounded for graphs with vertex degree at most $Delta$. In this paper, we distinguish representative subclasses of graphs with bounded vertex degree that have bounded band-, tree-, or clique-width. Our proofs are constructive and lead to efficient algorithms for a variety of NP-hard graph problems when restricted to those classes.