Computing width parameters of graphs: theory of commitments and development of practical algorithms

计算图的宽度参数：承诺理论和实用算法的开发

• 批准号: 26330021
• 负责人: Tamaki Hisao
• 金额: $ 3万
• 依托单位: Meiji University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2014
• 资助国家: 日本
• 起止时间: 2014-04-01 至 2018-03-31
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-26330021/
• 关键词: treewidth; trree-decomposition; exact algorithm; dynamic programming; positive-instance driven; safe separator; algorithm experiments; tree-decomposition; exact computation; heuristic computation; 木幅; 木分解; 正例駆動; 動的計画法; バス幅; パス分解; 整数計画法; 固

项目成果

Improved fixed parameter algorithm for two-layer crossing minimization

改进的两层交叉最小化固定参数算法

• 发表时间: 2015
• 作者: 橘内 謙太;小林 靖明;玉木 久夫;小林 靖明 玉木 久夫
• 通讯作者: 小林 靖明 玉木 久夫

Finalizing tentative matches from truncated preference lists

从截断的首选项列表中完成暂定匹配

• 发表时间: 2017
• 作者: 吉町優;真鍋義文;Hisao Tamaki
• 通讯作者: Hisao Tamaki

準完全有向グラフとその一般化に対するパス幅計算について

半完全有向图的路径宽度计算及其推广

• 发表时间: 2015
• 作者: 橘内 謙太;小林 靖明;玉木 久夫
• 通讯作者: 玉木 久夫

An Improved Fixed-Parameter Algorithm for One-Page Crossing Minimization

一种改进的单页交叉最小化固定参数算法

• DOI: 10.4230/lipics.ipec.2017.25
• 发表时间: 2017
• 期刊: 12th International Symposium on Parameterized and Exact Computation
• 作者: Yasuaki Kobayashi;Hiromu Ohtsuka;Hisao Tamaki
• 通讯作者: Hisao Tamaki

A faster fixed parameter algorithm for two-layer crossing minimization

一种更快的两层交叉最小化固定参数算法

• DOI: 10.1016/j.ipl.2016.04.012
• 发表时间: 2016
• 期刊: Information Processing Letters
• 影响因子: 0.5
• 作者: Yasuaki Kobayashi;Hisao Tamaki
• 通讯作者: Hisao Tamaki