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.

我们为任意图开发了一些足够的条件和算法，可以在多项式时间内解决最大的集团问题。这些算法可以在没有任何条件的任何任意图中找到一个精确的最大集合。我们还通过实验证实，我们新开发的另一种最大遇到的算法非常有效。这些算法有效地用于某些问题，如生物信息学中。

项目成果

Structural Change Pattern Mining Based on Constrained Maximal k-Plex Search

• DOI: 10.1007/978-3-642-33492-4_23
• 发表时间: 2012-10
• 作者: Yoshiaki Okubo;M. Haraguchi;E. Tomita

Polynomial time identification of strict prefix deterministic finitestate transducers

严格前缀确定性有限状态换能器的多项式时间辨识

• 发表时间: 2010
• 期刊: Lecture Notes in Computer Science
• 作者: Mitsuo Wakatsuki;Etsuji Tomita
• 通讯作者: Etsuji Tomita

本研究の重要な基礎をなす下記論文TCS2006は,「Theoretical Computer Science Top CitedArticle 2005-2010」表彰を受けた

本研究的重要基础论文《TCS2006》荣获“2005-2010年度理论计算机科学最高被引论文”奖。

数理モデルの応用技術 (情報処理学会50年のあゆみ, 第3編 中)

数学模型的应用技术（日本信息处理学会50年第3部分）

• 发表时间: 2010
• 作者: 中森眞理雄;富田悦次
• 通讯作者: 富田悦次

森北出版

森北出版社

• 发表时间: 2006
• 作者: 金森敬文;畑埜晃平;渡辺治
• 通讯作者: 渡辺治