NC-Algorithms for Graphs with Small Treewidth
NC-Algorithms for Graphs with Small Treewidth
复制标题
小树宽图的 NC 算法
DOI：
--
复制
发表时间：
1988
期刊：
影响因子：
--
通讯作者：
H. Bodlaender
中科院分区：
文献类型：
--
作者：
H. Bodlaender
在本文中，我们给出了一种平行算法，用于识别恒定k的树宽度≤k，并构建相应的树分解，该算法也使用O（log n）时间和O（n3k+4）处理器，我们给出了一种平行的算法，该算法将带有树宽k的图G的给定的树分解转换为G的另一棵树宽度分类的树宽度≤3k+2，因此该树的分解中的树是二进制的，并且具有对数深度。该算法使用线性数量的处理器，而O（log n）时间都可以在多项式时间内溶解，而限制在Treewidth≤k，k，k k，k，k的结果中。因此，这些问题中的大多数也位于NC中，仅限于以常数为界的树宽度的图。
In this paper we give a parallel algorithm for recognizing graphs with treewidth ≤ k, for constant k, and building the corresponding tree-decomposition, that uses O(log n) time and O(n3k+4) processors on a CRCW PRAM. Also, we give a parallel algorithm that transforms a given tree-decomposition of a graph G with treewidth k to another tree-decomposition of G with treewidth ≤ 3k+2, such that the tree in this tree-decomposition is binary and has logarithmic depth. The algorithm uses a linear number of processors and O(log n) time. Many NP-complete graph problems are known to be solvable in polynomial time, when restricted to graphs with treewidth ≤ k, k constant. From the results in this paper, it follows that most of these problems are also in NC, when restricted to graphs with treewidth bounded by a constant.