Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
复制标题
图的路径宽度和树宽度的高效且有建设性的算法
DOI：
10.1006/jagm.1996.0049
复制
发表时间：
1993
期刊：
影响因子：
--
通讯作者：
T. Kloks
中科院分区：
文献类型：
--
作者：
H. Bodlaender;T. Kloks
本文给出了对所有常数k，l的一个显式算法，即给定一个图G =（V，E），其树分解的树宽至多为l，判定G的树宽（或路宽）是否至多为k，如果是，则找出G的树宽（或路宽）至多为k的一个树分解，并使用O（|V|）时间。与以前的解决方案相比，我们的算法不依赖于非建设性的推理，是单指数inkandl。该结果可以与结果B组合。Reed在“Proceedings of the 24th Annual Symposium on Theory of Computing”，pp. 221？228，1992，产生显式O（nlogn）算法的问题，给定一个图G，以确定是否树宽（或路径宽度）ofG是在mostk，如果是这样，找到一个树（或路径）分解的宽度在mostk（k常数）。所以，H。L. Bodlaender在“Proceedings of the 25th Annual Symposium on Theory of Computing，”pp. 226？234，1993已经利用本文的结果得到了这些问题的线性时间算法。我们还表明，对于所有constantsk，存在一个多项式时间算法，当给定一个graphG=（V，E）与树宽？k，计算G的路径宽度和G的最小宽度的路径分解。
In this paper we give, for all constantsk,l, explicit algorithms that, given a graphG=(V,E) with a tree-decomposition ofGwith treewidth at mostl, decide whether the treewidth (or pathwidth) ofGis at mostk, and, if so, find a tree-decomposition (or path-decomposition) ofGof width at mostk, and that useO(|V|) time. In contrast with previous solutions, our algorithms do not rely on non-constructive reasoning and are single exponential inkandl. This result can be combined with a result of B. Reed in“Proceedings of the 24th Annual Symposium on Theory of Computing,” pp. 221?228, 1992, yielding explicitO(nlogn) algorithms for the problem, given a graphG, to determine whether the treewidth (or pathwidth) ofGis at mostk, and, if so, to find a tree- (or path-) decomposition of width at mostk(kconstant). Also, H. L. Bodlaender in“Proceedings of the 25th Annual Symposium on Theory of Computing,” pp. 226?234, 1993 has used the result of this paper to obtain linear time algorithms for these problems. We also show that for all constantsk, there exists a polynomial time algorithm that, when given a graphG=(V,E) with treewidth ?k, computes the pathwidth ofGand a path-decomposition ofGof minimum width.