Development of efficient algorithms for finding a maximum clique with theoretical and experimental evaluations and their applications

通过理论和实验评估及其应用开发寻找最大团的有效算法

• 批准号: 22500009
• 负责人: TOMITA Etsuji
• 金额: $ 2.66万
• 依托单位: The University of Electro-Communications
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2010
• 资助国家: 日本
• 起止时间: 2010 至 2012
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-22500009/
• 关键词: 最大クリーク; 極大クリーク; NP完全問題; 時間計算量; 多項式時間的可解性; 分枝限定法; バイオインフォマティクス; 計算機実験; データマイニング

We developed some sufficient conditions and algorithms for arbitrary graphs by which the maximum clique problem can be solved in polynomial time. These algorithms can find an exact maximum clique in any arbitrary graph without any condition. We also confirmed experimentally that our newly developed another maximum-clique-finding algorithm works very efficiently. These algorithms were effectively applied for some problems as in bioinformatics.

本文给出了任意图的最大团问题在多项式时间内求解的充分条件和算法。这些算法可以在任意图中无条件地找到一个精确的最大团。我们还通过实验证实了我们新开发的另一种最大团查找算法非常有效。这些算法有效地应用于生物信息学中的一些问题。

项目成果

A Simple and Faster Branch-and-Bound Algorithm for Finding a Maximum Clique with Computational Experiments

• DOI: 10.1587/transinf.e96.d.1286
• 发表时间: 2013-06
• 期刊: IEICE Trans. Inf. Syst.
• 作者: E. Tomita;Yoichi Sutani;Takanori Higashi;Mitsuo Wakatsuki

An Improved Clique-Based Method for Computing Edit Distance between Rooted Unordered Trees

一种改进的基于团的计算有根无序树之间编辑距离的方法

• 发表时间: 2011
• 作者: Tomoya Mori;Takeyuki Tamura;Daiji Fukagawa;Atsuhiro Takasu;Etsuji Tomita;Tatsuya Akutsu
• 通讯作者: Tatsuya Akutsu

疑似独立集合制約と正規化カットを用いたグラフの構造比較

使用伪独立集约束和归一化切割进行图结构比较

• 发表时间: 2013
• 作者: 村尾裕一;近藤祐史;兵頭礼子;齊藤友克;間澤直寛,原口誠,富田悦次
• 通讯作者: 間澤直寛,原口誠,富田悦次

オートマトン・言語理論(第22刷・改訂増刷)

自动机与语言理论（第22版，修订重印）

• 发表时间: 2011
• 作者: Hitoshi Furusawa;Yasuo Kawahara;Michael Winter;富田悦次・横森貴
• 通讯作者: 富田悦次・横森貴

最大クリーク問題の多項式時間的可解性の更なる改良結果

最大团问题多项式时间可解性的进一步改进结果

• 发表时间: 2011
• 期刊: 電子情報通信学会論文誌Ｄ
• 作者: 佐々木建昭; 稲葉大樹;中西裕陽，富田悦次，若月光夫，西野哲朗
• 通讯作者: 中西裕陽，富田悦次，若月光夫，西野哲朗