Inapproximability of graph width parameters

图宽度参数的不近似性

• 批准号: 24500007
• 负责人: Yamazaki Koichi
• 金额: $ 1.25万
• 依托单位: Gunma University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2012
• 资助国家: 日本
• 起止时间: 2012-04-01 至 2016-03-31
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-24500007/
• 关键词: グラフパラメータ; 近似困難性; Small Set Expansion 予想; rank-width; clique-width; boolean-width; SSE予想; vertex boundary-width; carving-width; 定数近似困難性; Path-Distance-Width; Tangle; 極小セパレータ; minimal separator; unit disk graph

项目成果

Tangleとイデアルについて

关于 Tangle 和 Ideal

• 发表时间: 2015
• 期刊: 数理解析研究所講究録
• 作者: M. Nakanishi;M. Matsuyama;and Y. Yokoo;山崎浩一
• 通讯作者: 山崎浩一

A revisit of the scheme for computing treewidth and minimum fill-in

重新审视计算树宽和最小填充的方案

• DOI: 10.1016/j.tcs.2014.03.013
• 发表时间: 2014
• 期刊: Theoretical Computer Science
• 影响因子: 1.1
• 作者: Masanobu Furuse;Koichi Yamazaki
• 通讯作者: Koichi Yamazaki

幅系グラフパラメータの近似について

关于宽度图参数的近似

• 发表时间: 2015
• 期刊: 信学技法 IEICE Technical Report COMP2015-2
• 作者: 岡崎 修;廣江道昭;諸井雅男;中村有妃子;岩野真依;中川 尭;脇屋桃子;春山亜希子;嘉陽 毅;岡崎 徹;池田長生;上村宗弘;伊藤信吾;山本正也;原 久男;廣井透雄;藤岡俊一郎;戸口孝治;福田尚司;保坂 茂;岡崎百子;宮田陽子;南本亮吾;諸岡 都;窪田和雄;山崎浩一
• 通讯作者: 山崎浩一

On 1 + $\epsilon$ strip graphs

在 1 $epsilon$ 带状图上

• 发表时间: 2012
• 期刊: IEICE Technical Report
• 作者: Takashi Hayashi;Hidehiro Shinohara;Koichi Yamazaki
• 通讯作者: Koichi Yamazaki

Tangleとイデアル

纠结与理想

• 发表时间: 2015
• 期刊: 信学技法 IEICE Technical Report COMP2014-51
• 作者: 石井梨奈;山崎健二;柴 昌徳;飯島雷輔;原 英彦;野呂眞人;諸井雅男;中村正人;杉 薫;鈴木真事;山崎浩一
• 通讯作者: 山崎浩一