最大クリークを抽出する単純なアルゴリズムとその最大時間計算量

新道 美喜男  富田 悦次  

誌名
電子情報通信学会論文誌 D   Vol.J71-D   No.3   pp.472-481
発行日: 1988/03/25
Online ISSN: 
DOI: 
Print ISSN: 0913-5713
論文種別: 論文
専門分野: アルゴリズム,計算複雑性
キーワード: 


本文: PDF(780.3KB)>>
論文を購入




あらまし: 
本論文では,節点数nの無向グラフ中の最大クリークを抽出する新しいアルゴリズムMAXCLIQUEを提唱し,その最大時間計算量がO(2n/2.863)となることを示している.これと双対な最大独立節点集合抽出問題に対しては,既にTarjanらによる最大時間計算量O(2n/3)のアルゴリズムがあるが,それと比べて本アルゴリズムは格段に単純であり,実際に両アルゴリズムが実働化していくつかのランダムグラフに対し平均実行時間を測定したところでは,本アルゴリズムの方がより高速であることを確認できた.