著者

宇野 毅明

出版者

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

雑誌

電子情報通信学会技術研究報告. COMP, コンピュテーション (ISSN:09135685)

巻号頁・発行日

vol.103, no.31, pp.55-62, 2003-04-18

被引用文献数

5

---

グラフG=(V, E)の頂点集合Sの任意の2頂点間に枝があるとき、Sをクリークとよぶ。また、2部グラフG=(V_1∪V_2, E)の頂点集合Sの任意の頂点v_1 ⋴ V_1とv_2 ⋴ V_2の間に枝があるとき、Sを2部クリークとよぶ。本稿では,巨大で疎なグラフ極大クリークと極大2部クリークを列挙する,実用的に高速なアルゴリズムを提案する。グラフの最大次数を△とすると,本稿の改良により,極大クリーク1つあたりの計算時間がO(|V||E|)からO(△^4)に,極大2部クリークはO(|V||E|)からO(△^3)に改善された。計算機実験により,ある程度ランダムな入力に対しては,1つあたりO (△^2)時間程度しかかからないことを示し、さらに現実のデータに対しても高速であることを示す。