论文标题
多项式时间算法来计算串联平行图的连接树宽度
A polynomial time algorithm to compute the connected tree-width of a series-parallel graph
论文作者
论文摘要
众所周知，图$ g $的树宽对应于节点搜索号码，其中一支警察团队正在追求一个懒惰，可见且具有无限速度行驶的强盗。在最近的论文中，已经考虑了连接的节点搜索策略。如果在每个步骤中，则连接搜索阶层，如果警察团队占领或已占领的一组顶点，则诱导了$ g $的连接子图。已经表明，图$ g $的连接搜索号可以表示为连接的树宽，表示为$ \ mathbf {ctw}（g），$，定义为均匀的树 - 代理$的最小宽度$（{{\ cal x}，t，t，t，t，r}）$ $ $ $ $ $ $ $的$ $ the $ nod a nod of the $已连接。显然，我们有$ \ mathbf {tw}（g）\ leqslant \ mathbf {ctw}（g）$。这是纸，我们启动了连接的树宽的算法研究。我们设计了$ O（n^2 \ cdot \ log n）$ - 时间动态编程算法来计算双连接串联串联图的连接树宽。我们的算法以额外的$ n $ factor为单位，最多最多为2美元。
It is well known that the treewidth of a graph $G$ corresponds to the node search number where a team of cops is pursuing a robber that is lazy, visible and has the ability to move at infinite speed via unguarded path. In recent papers, connected node search strategies have been considered. A search stratregy is connected if at each step the set of vertices that is or has been occupied by the team of cops, induced a connected subgraph of $G$. It has been shown that the connected search number of a graph $G$ can be expressed as the connected treewidth, denoted $\mathbf{ctw}(G),$ that is defined as the minimum width of a rooted tree-decomposition $({{\cal X},T,r})$ such that the union of the bags corresponding to the nodes of a path of $T$ containing the root $r$ is connected. Clearly we have that $\mathbf{tw}(G)\leqslant \mathbf{ctw}(G)$. It is paper, we initiate the algorithmic study of connected treewidth. We design a $O(n^2\cdot\log n)$-time dynamic programming algorithm to compute the connected treewidth of a biconnected series-parallel graphs. At the price of an extra $n$ factor in the running time, our algorithm genralizes to graphs of treewidth at most $2$.
