Designing low-congestion sparse networks
Designing low-congestion sparse networks
设计低拥塞稀疏网络
批准号：
23800004
负责人：
OTACHI Yota
金额：
$2.08万
依托单位国家：
日本
项目类别：
Grant-in-Aid for Research Activity Start-up
财政年份：
2011
资助国家：
日本
项目状态：
已结题
起止时间：
2011 至 2012
中文摘要
翻译
点击翻译按钮获取中文摘要
英文摘要
We studied the problem of designing low-congestion sparse networks. Especially, we studied the computational complexity of an optimization problem on graphs called “the spanning tree congestion problem.” We presented sharp contrasts between hard cases and easy cases. We also investigated the parameterized complexity of the problem and gave some dichotomies for the problem. Our results imply the problem is really hard to solve for most of the cases. Thus we designed some heuristic and approximation algorithm and obtained some partial results.
期刊论文(16)
专著(0)
科研奖励(0)
会议论文
登录
查看更多内容
DOI：
10.1016/j.jda.2011.11.001
发表时间：
2012
期刊：
Journal of Discrete Algorithms
影响因子：
--
作者：
[T. Saitoh, Y. Otachi, K. Yamanaka, and R. Uehara]
通讯作者：
and R. Uehara
DOI：
10.1007/s00453-011-9565-7
发表时间：
2011-09
期刊：
Algorithmica
影响因子：
1.1
作者：
[H. Bodlaender;F. Fomin;P. Golovach;Y. Otachi;E. J. V. Leeuwen]
通讯作者：
H. Bodlaender;F. Fomin;P. Golovach;Y. Otachi;E. J. V. Leeuwen
Approximating the path-distance-width for AT-free graphs and graphs in related classes
近似无 AT 图和相关类中的图的路径距离宽度
近似无 AT 图和相关类中的图的路径距离宽度
DOI：
10.1016/j.dam.2012.11.015
发表时间：
2013
期刊：
Discrete Applied Mathematics
影响因子：
1.1
作者：
[Yota Otachi, Toshiki Saitoh, Katsuhisa Yamanaka, Shuji Kijima, Yoshio Okamoto, Hirotaka Ono, Yushi Uno, and Koichi Yamazaki]
通讯作者：
and Koichi Yamazaki
Base location problems for base-monotone regions
基单调区域的基位置问题
基单调区域的基位置问题
DOI：
--
发表时间：
2013
期刊：
影响因子：
--
作者：
[J. Chun, T. Horiyama, T. Ito, N. Kaothanthong, H. Ono, Y.chi, T. Tokuyama, R. Uehara and T. Uno]
通讯作者：
R. Uehara and T. Uno
The path-distance-width of hypercubes
超立方体的路径-距离-宽度
超立方体的路径-距离-宽度
DOI：
10.7151/dmgt.1682
发表时间：
2013
期刊：
Discussiones Mathematicae Graph Theory
影响因子：
0.7
作者：
[Yaguchi, H., Okumura, F., Takahashi, H., Kano, T., Kameda, H., Uchigashima, M., Tanaka, S., Watanabe, M., Sasaki, H. and Hatakeyama, S., Yota Otachi]
通讯作者：
Yota Otachi
共 14 条
海外基金