The bandwidth minimization problem for caterpillars with hair length 3 is NP-complete
The bandwidth minimization problem for caterpillars with hair length 3 is NP-complete
复制标题
DOI：
10.1137/0607057
复制
发表时间：
1986-10
期刊：
影响因子：
--
通讯作者：
B. Monien
中科院分区：
文献类型：
--
作者：
B. Monien
结果表明，带宽最小化问题仍然是NP完全的，即使限制到“毛毛虫与头发的长度最多为三个”。“毛虫”是一种特殊的树，它们由一条简单的链（“身体”）和连接在身体顶点上的各种简单的链（连接的链称为“头发”）组成。在文献中的一个先前的结果表明，毛毛虫的毛长度最多为2的带宽可以在$O（n\log n）$时间内找到（本杂志，2（1981），pp. 387-393）。我们还表明，带宽问题是NP-完全时，仅限于毛虫与最多一根头发连接到身体的每个顶点。该证明相对简单，因此也提供了比在（SIAM J. Appl. Math.，34（1978），pp. 477-495），带宽问题是NP-完全的最大顶点度为3的树。
It is shown that the Bandwidth Minimization problem remains NP-complete even when restricted to “caterpillars with hairs of length at most three”. “Caterpillars” are special trees; they consist of a simple chain (the “body”) with various simple chains attached to thee vertices of the body (the attached chains are called “hairs”). A previous result in the literature shows that the bandwidth of caterpillars with hairs of length at most 2 can be found in $O( n\log n )$ time (this Journal, 2 (1981), pp. 387–393). We also show that the bandwidth problem is NP-complete when restricted to caterpillars with at most one hair attached to each vertex of the body. The proof is relatively straightforward and thereby also provides an easier proof than found in (SIAM J. Appl. Math., 34 (1978), pp. 477–495) that the bandwidth problem is NP-complete for trees with maximum vertex degree 3.