New Tools and Simpler Algorithms for Branchwidth
New Tools and Simpler Algorithms for Branchwidth
复制标题
用于分支宽度的新工具和更简单的算法
DOI：
--
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
J. A. Telle
中科院分区：
文献类型：
--
作者：
C. Paul;J. A. Telle
我们提供了新的工具，如k-troikas和良好的子树表示，使我们能够快速和简单的算法计算分支宽度。我们证明了图G具有至多k的分支宽度当且仅当它是弦图的子图，其中每个极大团都有k-三驾马车关于它的最小分离子。此外，如果G本身与团树T弦，则存在这样一个弦超图，其团树是T的子图。我们使用这些工具，给一个简单的O（m+n+q2）算法计算分支宽度的区间图的m条边，n个顶点和q个最大团。我们还证明了F的一个猜想。Mazoit [13]通过证明弦图上的分支宽度是多项式的，所述弦图具有具有多项式数目的子树的团树。
We provide new tools, such as k-troikas and good subtree-representations, that allow us to give fast and simple algorithms computing branchwidth. We show that a graph G has branchwidth at most k if and only if it is a subgraph of a chordal graph in which every maximal clique has a k-troika respecting its minimal separators. Moreover, if G itself is chordal with clique tree T then such a chordal supergraph exists having clique tree a minor of T. We use these tools to give a straightforward O(m+n+q2) algorithm computing branchwidth for an interval graph on m edges, n vertices and q maximal cliques. We also prove a conjecture of F. Mazoit [13] by showing that branchwidth is polynomial on a chordal graph given with a clique tree having a polynomial number of subtrees.