Improvement and extension of maximum-clique-finding algorithms with complexity analysis and their applications

复杂度分析最大团查找算法的改进和扩展及其应用

• 批准号: 19500010
• 负责人: TOMITA Etsuji
• 金额: $ 2.83万
• 依托单位: The University of Electro-Communications
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2007
• 资助国家: 日本
• 起止时间: 2007 至 2009
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-19500010/
• 关键词: 最大クリーク; 極大クリーク; 分枝限定法; 並列処理; NP完全問題; 時間計算量; 多項式時間的可解性; データマイニング; 計算機実験; NP困難問題; 計算論的学習理論; ハイパーグラフ; DNAコンピューティング; 分散処理

最大クリークを抽出する新しいアルゴリズムMCSを開発し,格段に高速であることを明らかにした.これにより,従来では100日以上かかっても解けなかった幾つかの問題を100秒以内で解くことに成功した.最大クリーク問題が多項式時間的に可解となる基本的結果も確立した.また,最大クリーク抽出アルゴリズムがハイパーグラフにおいても効率的に稼働する様に拡張した.更に,これらのアルゴリズムをデータマイニングなどの実問題に応用して有効な結果を得た.

我们开发了一种新的算法 MCS，用于提取最大派系，并且已经证明它的速度明显更快。通过这种算法，我们在不到 100 秒的时间内成功解决了几个传统上需要 100 多天才能解决的问题。建立了最大团问题在多项式时间内可解的基本结果。我们还扩展了最大团提取算法以在超图上高效工作。此外，我们将这些算法应用于数据挖掘，通过将其应用于实际问题，我们获得了有效的结果。例如

项目成果

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

• DOI: 10.1007/978-3-642-11440-3_18
• 发表时间: 2010-02
• 作者: E. Tomita;Yoichi Sutani;Takanori Higashi;Shinya Takahashi;Mitsuo Wakatsuki

Implementation Issues of Second-Order Cone Programming Approaches for Support Vector Machine Learning Problems

• DOI: 10.1587/transfun.e92.a.1209
• 发表时间: 2009-04
• 期刊: IEICE Trans. Fundam. Electron. Commun. Comput. Sci.
• 作者: R. Debnath;M. Muramatsu;Haruhisa Takahashi

インターナルクロックモデルに基づくロボット制御法の実現

基于内部时钟模型的机器人控制方法的实现

• 发表时间: 2007
• 期刊: 情報処理学会論文誌:数理モデル化と応用 48
• 作者: 眞鍋秀聡;西野哲朗;山崎匡;田中繁
• 通讯作者: 田中繁

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

自动机/语言理论（第20次印刷/修订重印）

• 发表时间: 2009
• 作者: 高橋治久;堀田一弘;富田悦次;広中平祐;富田 悦次
• 通讯作者: 富田 悦次

NetMCQ: A distributed exact maximum clique so lver

NetMCQ：分布式精确最大派系解决方案

• 发表时间: 2007
• 作者: S. Urabe;E. Tomita
• 通讯作者: E. Tomita