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.

对于嵌入亏格为g的可定向曲面的图G的分支分解，我们给出了一个（1+2g/3）-近似算法.这个结果是基于不等式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