孤立した部分グラフの列挙

概要

論文の詳細を見る
近年のよく知られたWebグラフの問題の1つとして、グループ内で密にリンクされているWebページのグループを見つける問題がある。クリークは明らかにそのようなグループの例と言える。しかしクリークを求める問題(最大のものを求める、極大のものを列挙する)のほとんどは難しく、良い近似方法もない。本稿では「孤立した」クリークとその一般化として孤立した部分グラフを紹介する。部分グラフが「孤立している」とは、内部で密にリンクされているだけでなく、その部分グラフと外部とのリンクが少ないことをいう。例えば、サイズだのクリークでは、外部への枝はκ-1本以下しか許されない。このような孤立条件により、多くの問題が簡単になり、孤立したクリークを列挙する問題が多項式時間で解くことができる。また、孤立したクリークよりやや密度の低い準クリークについても、平均次数がκ-logだ以上でかつ最小次数がκ/(logκ)以上である準クリークを多項式時間で列挙できることを示す。さらにこれらの一般化として、連結度を利用して孤立した一般の部分グラフを多項式時間で列挙できることも示す。
社団法人電子情報通信学会の論文
2004-04-15