Design and Analysis of Algorithms for Computationally Intractable Combinatorial Problems

计算难解组合问题的算法设计与分析

• 批准号: 20700011
• 负责人: TAMAKI Suguru
• 金额: $ 2万
• 依托单位: Kyoto University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Young Scientists (B)
• 财政年份: 2008
• 资助国家: 日本
• 起止时间: 2008 至 2010
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-20700011/
• 关键词: 計算量理論; アルゴリズム理論; 厳密アルゴリズム; 充足可能性問題; 計算困難性; 彩色問題; グラフ理論; 証明の複雑さ

Many practical optimization problems are known to be NP-hard, which is the class of computationally intractable problems. In this study, we gave design and complexity analysis of efficient exact algorithms for such computationally difficult problems. As a result, we obtained improved algorithms for the satisfiability problems (SAT) and the Boolean connectivity problems. We also gave characterizations of the complexity of the Boolean connectivity problems for Horn-SAT and the 3-colorability problems for planar graphs.

许多实际的优化问题都是NP难的，这是一类计算上难以解决的问题。在这项研究中，我们给出了设计和复杂性分析的高效精确算法，这样的计算困难的问题。在此基础上，得到了求解可满足性问题（SAT）和布尔连通性问题的改进算法。我们还给出了Horn-SAT的布尔连通性问题和平面图的3-可染性问题的复杂性的刻画。

项目成果

3SATに対する乱択アルゴリズムの改良

改进的 3SAT 随机选择算法

• 发表时间: 2010
• 作者: Kazuhisa Makino;Suguru Tamaki;Masaki Yamamoto.;玉置卓
• 通讯作者: 玉置卓

A query efficient non‐adaptive long code test with perfect completeness

• DOI: 10.1002/rsa.20549
• 发表时间: 2010-09
• 期刊: Random Structures & Algorithms
• 影响因子: 1
• 作者: Suguru Tamaki;Yuichi Yoshida

離散数学のすすめ

离散数学推荐

• 发表时间: 2010
• 作者: 吉田悠一;山本真基;伊藤大雄;K. Morita;伊藤大雄・宇野裕之
• 通讯作者: 伊藤大雄・宇野裕之

An exact algorithm for the Boolean connectivity problem for k-CNF

k-CNF 布尔连通性问题的精确算法

• DOI: 10.1016/j.tcs.2011.04.041
• 发表时间: 2011
• 期刊: Theor.Comput.Sci.
• 作者: K.Makino;S.Tamaki;M.Yamamoto
• 通讯作者: M.Yamamoto

計算量理論の最先端(離散数学のすすめ)(玉置卓)第16章

计算复杂性理论的前沿（离散数学推荐）（Taku Tamaki）第16章

• 发表时间: 2010
• 作者: 伊藤大雄;宇野裕之編著
• 通讯作者: 宇野裕之編著