効率的な極大クリーク抽出アルゴリズムの開発と計算量評価に関する研究

高效最大派系提取算法开发及计算复杂度评估研究

• 批准号: 60550259
• 负责人: 富田 悦次
• 金额: $ 1.34万
• 依托单位: The University of Electro-Communications
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for General Scientific Research (C)
• 财政年份: 1985
• 资助国家: 日本
• 起止时间: 1985 至 1986
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-60550259/
• 关键词: グラフ; 最大クリーク; 極大クリーク; 独立節点集合; アルゴリズム; NP完全問題; 時間計算量

1.これまでの研究において、グラフ中で最大クリークが存在する可能性の高い部分を見出す"番号付け"と名付けた前処理手法を組み込んだ新しい最大クリーク抽出アルゴリズムを提唱し、その有効性を実証してきた。本研究では更に引続いて、同様の前処理を再帰的に部分グラフに対しても適用してその効果を高め、しかもそれが過度の前処理手数増加を招かないように制御した最大クリーフ抽出アルゴリズムを開発し、その大きい改善性を実験的に確認した。2.前記のアルゴリズムに対する理論的計算量評価は困難であるため、その評価の行い易い単純な最大クリーク抽出アルゴリズムを提唱し、その最大時間計算量が節点数nのグラフに対して0(2^<n/2.863>)であることを与えた。本アルゴリズムは、これと双対な最大独立節点集合抽出問題に対するTarjan and Trojanowskiの最大時間計算量0(2^<n/3>)のアルゴリズムに対して同評価基準においては若干劣るが、本アルゴリズムはそれと比べて格段に単純であり、実際に両アルゴリズムを実働化して節点数400以内のいくつかのランダムグラフに対して平均実行時間を測定したところでは、本アルゴリズムがより高速であることを確認できた。3.前(2)の結果を基として、与えられたグラフ中の極大クリークを全て列挙する単純なアルゴリズムを提唱し、その最大時間計算量が節点数nのグラフに対して0(3^<n/3>)であることを与えた。この評価値は、節点数に関してこれ以上改善することができないことを示すことができ、その意味において最適なものである。4.番号付け手法によって最大クリークが存在する可能性の低い部分の探索は省略するような、近似最大クリーク抽出アルゴリズムを提唱し、その有効性を実験的に示した。

1. In this study, the highest probability of existence was found in the middle and middle of the study, and the highest probability of existence was found in the middle and middle of the study. In this study, we further investigate the application of the same pre-processing techniques to the improvement of the performance of pre-processing techniques. 2. In the previous paragraph, the theoretical calculation amount of the node number n was estimated to be 0(2 ^<n/2.863>), and the calculation amount of the maximum time was estimated to be 0(2^<n/2.863>). The maximum computation time of Tarjan and Trojan 0(2^<n/3>) for the maximum independent node set extraction problem is 0(2^<n/3>). The average running time of the system is determined within 400 nodes, and the system speed is confirmed. 3. The result of the previous (2) is that the maximum number of nodes in the list is 0(3 ^<n/3>), and the maximum number of nodes is 0(3^<n/3>). The evaluation of the number of nodes is related to the improvement of the number of nodes. 4. The search for the lowest possible part of the maximum number of hits is omitted, the approximate maximum number of hits is extracted, and the effectiveness of the hit is demonstrated.

项目成果

三間 慎介: 電子情報通信学会総合全国大会. 62. 1424 (1987)

Shinsuke Mima：全国电子、信息和通信工程师学会大会。62. 1424 (1987)

田中 亮: 電子情報通信学会コンピユテーシヨン研究. COMP87. 1-10 (1987)

田中亮：IEICE COMP87。

新道 美喜男: 電子通信学会回路とシステム研究会. CAS86. 33-40 (1986)

Mikio Shinmichi：IEICE 电路和系统研究组。33-40 (1986)。

新道 美喜男: 電子通信学会コンピユテーシヨン研究会. COMP86. 59-68 (1986)

Mikio Shinmichi：IEICE COMP86。

富田 悦次: 電子通信学会コンプレクシテイ研究会. COMPLEX86. 1-26 (1986)

Etsuji Tomita：IEICE复杂性研究小组1-26（1986）。