最大クリークを抽出する単純で効率的な分枝限定アルゴリズムと実験的評価

富田 悦次  今松 憲一  木幡 康弘  若月 光夫  

誌名
電子情報通信学会論文誌 D   Vol.J79-D1   No.1   pp.1-8
発行日: 1996/01/25
Online ISSN: 
DOI: 
Print ISSN: 0915-1915
論文種別: 論文
専門分野: アルゴリズム,計算複雑性
キーワード: 
最大クリーク,  深さ優先探索,  分枝限定法,  近似彩色,  

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




あらまし: 
本論文では,無向グラフ中の最大クリークを抽出するための単純で効率の良い分枝限定アルゴリズムを提唱する.ここで,いかにして分枝の制限を強力に働かせて解の探索領域を小さくするかが,アルゴリズムの効率化の重要な指標となる.しかし,その分枝制限実現のために要する処理時間をできるだけ小さく抑える必要がある.そこで本論文では,その両者の兼合いを適切に達成した,非常に単純で巧妙な逐次近似彩色-整列法を考案し,それにより探索の各段階において見出し得る最大クリークの上界を得て分枝制限を効果的に実現し,総実行時間も小さく抑えることに成功した.本アルゴリズムは,他のいくつかの代表的アルゴリズムと直接実験的比較,あるいは論文上の数値比較により,それらに対して600節点以内の広い範囲の多くのランダムグラフおよび1000節点のいくつかのランダムグラフについて,より高速であることを確認した.