Extending the branch-decomposition algorithm for planar graphs to broader class of graphs

将平面图的分支分解算法扩展到更广泛的图类

• 批准号: 20500022
• 负责人: TAMAKI Hisao
• 金额: $ 1.33万
• 依托单位: Meiji University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2008
• 资助国家: 日本
• 起止时间: 2008 至 2010
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-20500022/
• 关键词: アルゴリズム; グラフ; 分枝分割; 分枝幅; グラフマイナー; 向き付け可能表面; 種数; グラフ理論; 組み合わせ最適化; 平面グラフ

We have developed a (1+2g/3)-approximation algorithm for the branch-decomposition of graph G embedded in an orientable surface of genus g. This result is based on an inequality bw(G)≧(3/2)fw(G), where bw(G) is the branchwidth of G and fw (G) is the face-width of G. We also have shown the inequality bw(G)≦3gm (G) for planar graphs, where gm(G) is the size of the largest grid minor of G and, based on this inequality, have developed a fast constant-factor approximation algorithm for the branch-decomposition of planar graphs.

我们开发了一种（1+2g/3）近似算法，用于嵌入在G属可定向曲面上的图G的分支分解。该结果基于不等式bw(G)≧(3/2)fw(G)，其中bw(G)为G的分支宽度，fw(G)为G的面宽。我们还展示了平面图的不等式bw(G)≦3gm (G)，其中gm(G)为G的最大网格次元的大小，基于该不等式，开发了一种用于平面图形分支分解的快速常因子近似算法。

项目成果

Constant-factor approximations of branch-decomposition and largest grid minor of planar graphs in O(n^<1+ε>)time

O(n^<1+ε>) 时间内平面图的分支分解和最大网格次要常数因子近似

• 发表时间: 2009
• 期刊: SFU Computing Science Technical Report 2009-18
• 作者: Q.-P.Gu;H.Tamaki
• 通讯作者: H.Tamaki

A radius-based linear-time constructive upper bound on the branchwidth of planar hypergraphs

平面超图分支宽度的基于半径的线性时间建设性上限

• 发表时间: 2009
• 期刊: SFU Computing Science Technical Report 2009-21
• 作者: Q.-P.Gu;H.Tamaki
• 通讯作者: H.Tamaki

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

• DOI: 10.1145/1367064.1367070
• 发表时间: 2005-07
• 期刊: ACM Trans. Algorithms
• 作者: Q. Gu;H. Tamaki

Efficient reduction of vertex-disjoint Menger problem to edge-disjoint Menger problem in undirected planar graphs

无向平面图中顶点不相交门格尔问题有效简化为边不相交门格尔问题

• 发表时间: 2009
• 期刊: SFU Computing Science Technical Report 2009-11
• 作者: Q.-P.Gu;H.Tamaki
• 通讯作者: H.Tamaki

k-Cyclic Orientations of Graphs

图的 k 循环方向

• 发表时间: 2010
• 期刊: Proc.21st International Symposium on Algorithms and Computation
• 作者: Yasuaki Kobayashi;Yuichiro Miyamoto;Hisao Tamaki
• 通讯作者: Hisao Tamaki