Combinatorial generation with fixed-parameter tractable preprocessing

具有固定参数易处理预处理的组合生成

• 批准号: 18K11174
• 负责人: Tamaki Hisao
• 金额: $ 2.75万
• 依托单位: Meiji University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2018
• 资助国家: 日本
• 起止时间: 2018-04-01 至 2023-03-31
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-18K11174/
• 关键词: algorithm; graph parameter; treewidth; tree-decomposition; enumeration; preprocessing; minor; lower bound; 組み合わせ列挙; 固定パラメータアルゴリズム; 前処理; 木幅; BT法; 上界; 下界; グラフの縮約; 木分解; 潜在極小クリーク; マイナー; パス的木分解; 安全なセパレータ; ほぼクリークセパレータ; fixed parameter; ex

项目成果

Treewidth algorithm repository

树宽算法库

Heuristic Computation of Exact Treewidth

精确树宽的启发式计算

• 发表时间: 2022
• 期刊: 20th International Symposium on Experimental Algorithms
• 作者: Kazuyuki Asada;Naoki Kobayashi;Hisao Tamaki
• 通讯作者: Hisao Tamaki

Experimental Analysis of Treewidth

树宽实验分析

• DOI: 10.1007/978-3-030-42071-0_15
• 发表时间: 2020
• 期刊: Lecture Notes in Computer Science
• 作者: Gima Tatsuya;Hanaka Tesshu;Kiyomi Masashi;Kobayashi Yasuaki;Otachi Yota;Hisao Tamaki
• 通讯作者: Hisao Tamaki

Listing minimal separators for treewidth computation

列出树宽计算的最小分隔符

• 发表时间: 2018
• 作者: Jion Hirose;Junya Nakamura;Fukuhito Ooshita;and Michiko Inoue;Hisao Tamaki
• 通讯作者: Hisao Tamaki

Computing Treewidth via Exact and Heuristic Lists of Minimal Separators

通过最小分隔符的精确和启发式列表计算树宽

• DOI: 10.1007/978-3-030-34029-2_15
• 发表时间: 2019
• 期刊: Lecture Notes in Computer Science
• 作者: Ryota Kawasumi;Koujin Takeda;HIsao Tamaki
• 通讯作者: HIsao Tamaki