Tangle bases: Revisited
Tangle bases: Revisited
复制标题
缠结基地：重新审视
DOI：
10.1002/net.21979
复制
发表时间：
2020
期刊：
影响因子：
2.1
通讯作者：
Brimkov, Boris
中科院分区：
文献类型：
--
作者：
Hicks, Illya V.;Brimkov, Boris
分支分解的概念最早是由Robertson和Seymour在他们的图子定理的证明中引入的，并且可以被看作是图的全局连通性的度量。从那时起，分支分解和分支宽度已被用于计算解决组合优化问题的图形和拟阵建模。一般分支宽度是分支宽度的扩展到定义在有限集上的任何对称子模函数。一般分支宽度包括图形分支宽度、拟阵分支宽度和秩宽度。缠结基与缠结有关，这也是罗伯逊和西摩引入的概念;然而，缠结基在本质上更具建设性。它显示在[I。维·希克斯图形、分支宽度和缠结！哦，天哪！Networks，45：55 - 60，2005]，一个tangle基的序kis共延到一个tangle的序k。在本文中，我们重新计算其他branchwidth参数的缠结基础的建设，并表明缠结基础的方法仍然是有竞争力的计算一般branchwidth的最佳分支分解。
The concept of branch decomposition was first introduced by Robertson and Seymour in their proof of the Graph Minors Theorem, and can be seen as a measure of the global connectivity of a graph. Since then, branch decomposition and branchwidth have been used for computationally solving combinatorial optimization problems modeled on graphs and matroids. General branchwidth is the extension of branchwidth to any symmetric submodular function defined over a finite set. General branchwidth encompasses graphic branchwidth, matroidal branchwidth, and rankwidth. A tangle basis is related to a tangle, a notion also introduced by Robertson and Seymour; however, a tangle basis is more constructive in nature. It was shown in [I. V. Hicks. Graphs, branchwidth, and tangles! Oh my!Networks, 45:55‐60, 2005] that a tangle basis of orderkis coextensive to a tangle of orderk. In this paper, we revisit the construction of tangle bases computationally for other branchwidth parameters and show that the tangle basis approach is still competitive for computing optimal branch decompositions for general branchwidth.
登录
查看更多内容
图形拟阵的分支宽度
DOI：
10.1017/cbo9780511666209.010
发表时间：
2007
期刊：
--
影响因子：
--
作者：
Frédéric Mazoit;Stéphan Thomassé
通讯作者：
Stéphan Thomassé
影响因子：
--
作者：
BERN, MW;LAWLER, EL;WONG, AL
通讯作者：
WONG, AL
用于分支宽度的新工具和更简单的算法
DOI：
--
发表时间：
2005
期刊：
Embedded Systems and Applications
影响因子：
--
作者：
C. Paul;J. A. Telle
通讯作者：
J. A. Telle
射影平面的库拉托夫斯基定理
影响因子：
0.9
作者：
D. Archdeacon
通讯作者：
D. Archdeacon
分支宽度最多为 3 的图
DOI：
--
发表时间：
1999
期刊：
J. Algorithms
影响因子：
--
作者：
H. Bodlaender;D. Thilikos
通讯作者：
D. Thilikos