Optimal branch-decomposition of planar graphs in O(n3) Time

Optimal branch-decomposition of planar graphs in O(n3) Time
复制标题

DOI：
10.1145/1367064.1367070
复制
发表时间：
2005-07
期刊：
ACM Trans. Algorithms
影响因子：
--
通讯作者：
Q. Gu;H. Tamaki
Q. Gu;H. Tamaki
中科院分区：
其他
文献类型：
--
作者：
Q. Gu;H. Tamaki

文献摘要

被引文献

相似文献

我们给出了一个O（n3）时间算法来构造给定的n个顶点的平面图的最小宽度分支分解。这是通过对以前最著名的Seymour和Thomas算法的改进来实现的，该算法运行时间为O（n4）。
We give an O(n3) time algorithm for constructing a minimum-width branch-decomposition of a given planar graph with n vertices. This is achieved through a refinement to the previously best known algorithm of Seymour and Thomas, which runs in O(n4) time.