A study of graph width parameters

图宽度参数的研究

• 批准号: 21500004
• 负责人: YAMAZAKI Koichi
• 金额: $ 1.25万
• 依托单位: Gunma University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2009
• 资助国家: 日本
• 起止时间: 2009 至 2011
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-21500004/
• 关键词: 木幅; パス幅; パス距離幅; 近似アルゴリズム; グラフパラメータ; tree-width

The purpose of this study is to design approximation algorithms for tree-width, branch-width, bandwidth, path-width, and so on by considering its duality. As the result of the study, we showed that the distance path width of AT-free graphs can be approximated within a constant factor in polynomial time. Moreover, by considering the duality, we gave lower bounds for tree-width for Cartesian products of graphs, and extended the notion of forbidden structure for path-width to matroids.

本研究的目的是设计近似算法的树宽，分支宽度，带宽，路径宽度，等等，通过考虑其对偶。作为研究的结果，我们证明了AT-自由图的距离路径宽度可以在多项式时间内近似为一个常数因子。此外，通过考虑图的对偶性，给出了图的笛卡尔积的树宽的下界，并将路宽的禁止结构的概念推广到拟阵。

项目成果

Reformulation of the scheme for computing tree-width and minimum fill-in

计算树宽和最小填充方案的重新制定

• 发表时间: 2009
• 期刊: Proc.of 7th Japan Conference on Computational Geometry and Graphs
• 作者: Nguyen Khanh Long;Keizo Kato;Tomomi Yamashita;Hiroki Makita;Makoto Toida;Daijiro Hatakeyama;Akira Hara;Hideki Mori;Toshiyuki Shibata;Masanobu Furuse
• 通讯作者: Masanobu Furuse

Outerplanar Obstructions for Matroid Pathwidth

拟阵路径宽度的外平面障碍物

• 发表时间: 2011
• 期刊: Electronic Notes in Discrete Mathematics
• 作者: A. Koutsonas;D. M. Thilikos;K. Yamazaki
• 通讯作者: K. Yamazaki

Approximability of the path-distance width for AT-free graphs

无 AT 图的路径距离宽度的近似性

• 发表时间: 2011
• 作者: Yota Otachi;Toshiki Saitoh;Katsuhisa Ymanaka;Shuji Kijima;Yoshio Okamoto;Hirotaka Ono;Yushi Uno and Koichi Yamazaki
• 通讯作者: Yushi Uno and Koichi Yamazaki

カット幅の双対定理について

关于切割宽度的对偶定理

• 发表时间: 2011
• 期刊: 数理解析研究所講究録
• 作者: 片平明;桑原勇人;長澤亮介;大舘陽太;山崎浩一
• 通讯作者: 山崎浩一

A lower bound for tree-width of Cartesian product graphs

笛卡尔积图树宽的下界

• 发表时间: 2009
• 期刊: 6th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications, Proc. of JH 2009
• 作者: K. Kozawa;Y. Otachi;K. Yamazaki
• 通讯作者: K. Yamazaki