著者

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

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会論文誌. D-I, 情報・システム, I-コンピュータ (ISSN:09151915)

巻号頁・発行日

vol.79, no.1, pp.1-8, 1996-01-25

被引用文献数

13

---

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