Connected Treewidth and Connected Graph Searching
Connected Treewidth and Connected Graph Searching
复制标题
连通树宽度和连通图搜索
DOI：
--
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
Nicolas Nisse
中科院分区：
文献类型：
--
作者：
P. Fraigniaud;Nicolas Nisse
给出了树宽与连通树宽相等的构造性证明。更准确地说，我们描述了一个O（nk 3）时间算法，给定连通图G的任何n-节点宽度k树分解，返回G的宽度≤ k的连通树分解。树宽和连通树宽之间的相等性在图搜索问题中得到应用。首先，利用树宽与连通树宽的等价性，证明了连通图G的连通搜索数cs（G）至多是其搜索数的logn+1倍.其次，利用我们的树宽和连接树宽相等的构造性证明，我们设计了一个O（log nsqrt{log OPT}$）-连通搜索的近似算法，对于树宽最大为k的n节点m边连通图，时间复杂度为O（t（n）+nk 3log 3/2k+mlog n），其中t（n）是近似树宽的最快算法的时间复杂度，最高为$O（sqrt{log OPT}$）。
We give a constructive proof of the equality between treewidth and connected treewidth. More precisely, we describe an O(nk3)-time algorithm that, given any n-node width-k tree-decomposition of a connected graph G, returns a connected tree-decomposition of G of width ≤ k. The equality between treewidth and connected treewidth finds applications in graph searching problems. First, using equality between treewidth and connected treewidth, we prove that the connected search number cs(G) of a connected graph G is at most logn+1 times larger than its search number. Second, using our constructive proof of equality between treewidth and connected treewidth, we design an $O(log nsqrt{log OPT}$)-approximation algorithm for connected search, running in time O(t(n)+nk3log3/2k+mlog n) for n-node m-edge connected graphs of treewidth at most k, where t(n) is the time-complexity of the fastest algorithm for approximating the treewidth, up to a factor $O(sqrt{log OPT}$).