平成17年度第2回KSMAP

日時：2005年 11月8日（火） 15:00〜18:00
場所：京都大学 本部構内 工学部総合校舎 総合213講義室
  
講演題目と講演者：
・ 伊藤 大雄（京都大学大学院 情報学研究科 通信情報システム専攻）
  「孤立クリークの線形時間列挙」講演要旨

・ 永持 仁（京都大学大学院 情報学研究科 数理工学専攻）
  「私の履歴書」

孤立クリークの線形時間列挙
伊藤 大雄（京都大学大学院 情報学研究科 通信情報システム専攻）

クリークSの節点数がkであるとき、そのクリークと外部との 間の枝数がckより少ないとき、c-孤立クリークであるという ことにする。ここにcを孤立因数と呼ぶが、これがクリーク 発見および列挙に対し興味深い性質を持つことを示す。
特に

1. cが定数であるときグラフのサイズの線形時間で全ての c-孤立クリークを列挙することができ、
2. c=O(log n)であるときグラフのサイズの多項式時間で全ての c-孤立クリークを列挙することができる。
さらに
3. cが定数で押さえられない増加関数であるならば超線形個の c-孤立クリークが存在するグラフがあり、
4. c=ω(log n)ならば超多項式個のc-孤立クリークが存在する グラフがある。

すなわち、このアルゴリズムは、c-孤立クリークの線形時間 列挙、多項式時間列挙に関して最適なアルゴリズムである。