Algorithms for width-parameters of digraphs and their applications

有向图宽度参数算法及其应用

• 批准号: 23500026
• 负责人: TAMAKI Hisao
• 金额: $ 2.91万
• 依托单位: Meiji University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2011
• 资助国家: 日本
• 起止时间: 2011 至 2013
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-23500026/
• 关键词: 有向グラフ; パス幅; 固定パラメータアルゴリズム; 厳密指数時間アルゴリズム; グラフ; 木幅; 分枝幅; 表面埋め込み; 種数; グラフアルゴリズム; 木分割; パス分割; グラフ分割

For the problem of computing the pathwidth of digraphs, an XP algorithm (with running time n to the O(k), where n is the number of vertices and k is the pathwidth, and an algorithm with running time O(1.89 to the nth), were developed. The first version of the XP algorithm contained an essential flaw, and a considerable amount of time was spent for fixing the error. As applications, FPT algorithms for two-layer graph drawing problems were developed.

对于有向图的路径宽度计算问题，提出了一个运行时间为n到O(K)的XP算法和一个运行时间为O(1.89到n次)的算法。XP算法的第一个版本包含一个重要的缺陷，并且花费了相当多的时间来修复该错误。作为应用，开发了两层图绘制问题的FPT算法。

项目成果

A Linear Edge Kernel for Two-Layer Crossing Minimization

一种用于两层交叉最小化的线性边核

• 发表时间: 2013
• 期刊: COCOON
• 作者: Yasuaki Kobayashi;Hirokazu Maruta;Yusuke Nakae;Hisao Tamaki
• 通讯作者: Hisao Tamaki

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

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

• 发表时间: 2011
• 期刊: Theor. Comput. Sci
• 作者: Qian-Ping Gu;Hisao Tamaki
• 通讯作者: Hisao Tamaki

Computing Directed Pathwidth in O(1.89^ n ) Time

在 O(1.89^ n ) 时间内计算定向路径宽度

• 发表时间: 2012
• 期刊: IPEC 2012
• 作者: Kenta Kitsunai;Yasuaki Kobayashi;Keita Komuro;Hisao Tamaki;Toshihiro Tano
• 通讯作者: Toshihiro Tano

Computing Directed Pathwidth in O(1.89 n ) Time

在 O(1.89 n ) 时间内计算定向路径宽度

• 发表时间: 2011
• 期刊: IPEC 2012
• 作者: Kenta Kitsunai;Yasuaki Kobayashi;Keita Komuro;Hisao Tamaki;Toshihiro Tano
• 通讯作者: Toshihiro Tano

Route-Enabling Graph Orientation Problems

路由启用图方向问题

• DOI: 10.1007/s00453-011-9589-z
• 发表时间: 2013
• 期刊: Algorithmica
• 影响因子: 1.1
• 作者: Takehiro Ito;Yuichiro Miyamoto;Hirotaka Ono;Hisao Tamaki;Ryuhei Uehara
• 通讯作者: Ryuhei Uehara