効率的な最大および極大クリーク抽出アルゴリズムの開発と応用

高效最大派系提取算法的开发与应用

• 批准号: 17K00006
• 负责人: 富田 悦次
• 金额: $ 2.91万
• 依托单位: The University of Electro-Communications
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2017
• 资助国家: 日本
• 起止时间: 2017 至 2021
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-17K00006/
• 关键词: 最大クリーク; 極大クリーク; 深さ優先探索; 分枝限定アルゴリズム; 列挙; 近似アルゴリズム; 時間計算量; 符号理論; 分枝限定; アルゴリズム; 遅延; 多項式時間; 最大独立節点集合; 厳密解法; 近似解法; 実働評価; NP完全問題; 時間計算量解析; 多項式時間的可解性; 実働化評価; 分枝限定法

最大クリーク抽出は多くの実応用問題解決に対して有用であるがNP困難問題であり，一般的には求解に非常に長時間を要する．最大クリーク厳密解抽出の分枝限定アルゴリズムに対するこれまでの研究により，最大クリークの近似解が非常に有効に活用出来ることを明らかにしてきた．その近似精度が良くなれば分枝限定はより有効に働く．しかし，近似解抽出のために時間を要すると，総実行時間としては必ずしも短縮とはならず，近似精度と時間との兼ね合いが重要となる．そこで先ず，最大クリーク近似解の抽出を一層高速化し，その上で精度を向上させることにより，総合的に最大クリーク厳密解抽出を効率化した．続いて，分枝限定のために近似彩色だけでなくMaxSATも用いることにより分枝限定がより強力化されることをこれまでに確認してきたが，MaxSATあるいはその簡略形実行のためのオーバーヘッドの大きさが最大クリーク厳密解抽出総実行時間短縮の妨げとなっていた．これに対しては，MaxSATの簡略形と従来提唱してきていた再番号付け（再彩色）との類似性に着目して両者を融合させることにより，これまでよりも少ないオーバーヘッドによって，有効な分枝限定効果を発揮出来るようにした．さらに，分枝限定アルゴリズムの内部動作は入力グラフの特徴に応じて効率が左右されるため，出来る限り効率がより発揮されるようにと内部動作を適応的に切り替えるようにした．以上を総合することにより，最大クリーク厳密解抽出のための従来の分枝限定アルゴリズムを有意に高速化することに成功した．このような最大クリーク厳密解抽出アルゴリズムは，容易に最大クリーク全列挙アルゴリズムへと拡張出来る．これにより，符号理論における最良な多元単一削除訂正符号の構成に関しての新たな知見を得ることが出来た．また，極大クリーク全列挙問題についても理論的，実験的に検討を行い，有効な進展結果を得た．

It is very important to solve NP problems for a long time, but it is very important to solve the problem for a long time. The approximate solution of the maximum linear equation is very useful. The approximate accuracy is good. The branch limits the accuracy of the approximate solution. The time of the approximate solution is limited. The time of the approximate solution is very short. The approximate precision is the same as that of the important one. The maximum accuracy of the approximate solution is high-speed, the accuracy of the upper part is higher, the accuracy is higher, the maximum accuracy is higher, the accuracy is higher, the maximum accuracy is higher, the In MaxSAT, you need to know how much time it takes to extract a short message. You can use a short message in MaxSAT to sing the message that you want to rename your license number (re-color). The property is similar to that of the target user. There is a branch limit. The branch is limited. The branch is limited. There is a limit on the rate, the rate, the speed, the rate, the It is easy to make a full list of problems in order to get out of the theory. in terms of symbol theory, symbol theory and symbol theory, it is easy to remove the correct symbols into new information. In this case, you can get a lot of information about the whole range of problems. In terms of the theory of theory, you can learn more about the results of the improvement.

项目成果

最大クリーク問題に対する探索頻度情報にもとづく反復k-opt局所探索法の性能

基于搜索频率信息的迭代k-opt局部搜索方法求解最大团问题的性能

• 发表时间: 2019
• 期刊: 人工知能学会研究会資料
• 作者: 金原一歩;片山謙吾;富田悦次;松崎空良
• 通讯作者: 松崎空良

Speeding-Up of Construction Algorithms for the Graph Coloring Problem

图着色问题的构造算法加速

• 发表时间: 2020
• 作者: Kazuho Kanahara;Kengo Katayama;Takafumi Miyake;Etsuji Tomita
• 通讯作者: Etsuji Tomita

Enumeration of maximum cliques and its application to coding theory

最大团的枚举及其在编码理论中的应用

• 发表时间: 2019
• 作者: 金原一歩;片山謙吾;富田悦次;松崎空良;Etsuji Tomita
• 通讯作者: Etsuji Tomita

Efficient algorithms for finding maximum and maximal cliques

寻找最大和最大派系的有效算法

• 发表时间: 2017
• 作者: 長尾篤樹;松崎空良;富田悦次;伊藤大雄;若月光夫;西野哲朗;光武 朗，野崎隆之，富田悦次;Etsuji Tomita
• 通讯作者: Etsuji Tomita

富田悦次研究室 ホームページ

富田悦二实验室主页