Algorithms for width-parameters of digraphs and their applications
Algorithms for width-parameters of digraphs and their applications
有向图宽度参数算法及其应用
批准号：
23500026
负责人：
TAMAKI Hisao
金额：
$2.91万
依托单位：
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (C)
财政年份：
2011
资助国家：
日本
项目状态：
已结题
起止时间：
2011 至 2013
中文摘要
翻译
点击翻译按钮获取中文摘要
英文摘要
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.
期刊论文(0)
专著(0)
科研奖励(0)
会议论文
登录
查看更多内容
A Linear Edge Kernel for Two-Layer Crossing Minimization
一种用于两层交叉最小化的线性边核
一种用于两层交叉最小化的线性边核
DOI：
--
发表时间：
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+ϵ>) 时间内平面图的分支分解和最大网格次要常数因子近似
O(n^<1+ϵ>) 时间内平面图的分支分解和最大网格次要常数因子近似
DOI：
--
发表时间：
2011
期刊：
Theor. Comput. Sci
影响因子：
--
作者：
[Qian-Ping Gu, Hisao Tamaki]
通讯作者：
Hisao Tamaki
Computing Directed Pathwidth in O(1.89^ n ) Time
在 O(1.89^ n ) 时间内计算定向路径宽度
在 O(1.89^ n ) 时间内计算定向路径宽度
DOI：
--
发表时间：
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 ) 时间内计算定向路径宽度
在 O(1.89 n ) 时间内计算定向路径宽度
DOI：
--
发表时间：
2011
期刊：
IPEC 2012
影响因子：
--
作者：
[Kenta Kitsunai, Yasuaki Kobayashi, Keita Komuro, Hisao Tamaki, Toshihiro Tano]
通讯作者：
Toshihiro Tano
DOI：
10.1007/s00453-011-9589-z
发表时间：
2013
期刊：
Algorithmica
影响因子：
1.1
作者：
[Takehiro Ito, Yuichiro Miyamoto, Hirotaka Ono, Hisao Tamaki, Ryuhei Uehara]
通讯作者：
Ryuhei Uehara
共 11 条
Extending the branch-decomposition algorithm for planar graphs to broader class of graphs
-
批准号：20500022
-
项目类别：Grant-in-Aid for Scientific Research (C)
-
资助金额：$1.33万
-
财政年份：2008
-
负责人：TAMAKI Hisao
-
依托单位：
Polynomial time algorithm for dualizing a monotone DNF
-
批准号：10680365
-
项目类别：Grant-in-Aid for Scientific Research (C)
-
资助金额：$0.83万
-
财政年份：1998
-
负责人：TAMAKI Hisao
-
依托单位：
Approximation algoirithms for route optimization problems : exploiting geometric structures and application to large scale problems
-
批准号：10205225
-
项目类别：Grant-in-Aid for Scientific Research on Priority Areas (B)
-
资助金额：$5.76万
-
财政年份：1998
-
负责人：TAMAKI Hisao
-
依托单位：
海外基金