| 講演名 | 2004/4/15 孤立した部分グラフの列挙 大隅 剛史, 伊藤 大雄, 岩間 一雄, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 近年のよく知られたWebグラフの問題の1つとして、グループ内で密にリンクされているWebページのグループを見つける問題がある。クリークは明らかにそのようなグループの例と言える。しかしクリークを求める問題(最大のものを求める、極大のものを列挙する)のほとんどは難しく、良い近似方法もない。本稿では「孤立した」クリークとその一般化として孤立した部分グラフを紹介する。部分グラフが「孤立している」とは、内部で密にリンクされているだけでなく、その部分グラフと外部とのリンクが少ないことをいう。例えば、サイズだのクリークでは、外部への枝はκ-1本以下しか許されない。このような孤立条件により、多くの問題が簡単になり、孤立したクリークを列挙する問題が多項式時間で解くことができる。また、孤立したクリークよりやや密度の低い準クリークについても、平均次数がκ-logだ以上でかつ最小次数がκ/(logκ)以上である準クリークを多項式時間で列挙できることを示す。さらにこれらの一般化として、連結度を利用して孤立した一般の部分グラフを多項式時間で列挙できることも示す。 |
| 抄録(英) | One of the recently popular problems on the web graph is to find groups of web pages which are densely linked inside each group. Cliques are obviously a natural model for such groups. Unfortunately, however, most problems regarding cliques, such as finding a maximum one and enumerating maximal ones, are intractable. There is no good approximation, either. In this paper, we introduce "isolated" cliques or isolated subgraphs in general, for which we require not only that each subgraph is densely linked inside but also that each subgraph has few links to the outside. Typically, if the clique is of size fc, then only κ-1 or less edges to the outside are allowed. Our main results show that such an isolation condition makes many problems surprisingly easy. Problems like enumerating isolated cliques can be solved in polynomial time, and isolated pseudo cliques (which are less dense than cliques) which have average degrees at least κ-log κ and minimum degrees at least κ/(logκ) also can be enumerated in polynomial time. More, in general, we show that isolated subgraphs can be enumerated in polynomial time by considering edge-connectivities. |
| キーワード(和) | グラフ / Web / 数え上げ / クリーク / カット |
| キーワード(英) | graph / Web / enumeration / clique / cut |
| 資料番号 | COMP2004-5 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 2004/4/15(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | 孤立した部分グラフの列挙 |
| サブタイトル（和） | |
| タイトル（英） | Enumerating Isolated Subgraphs |
| サブタイトル（和） | |
| キーワード(1)（和/英） | グラフ / graph |
| キーワード(2)（和/英） | Web / Web |
| キーワード(3)（和/英） | 数え上げ / enumeration |
| キーワード(4)（和/英） | クリーク / clique |
| キーワード(5)（和/英） | カット / cut |
| 第 1 著者 氏名（和/英） | 大隅 剛史 / Tsuyoshi OSUMI |
| 第 1 著者 所属（和/英） | 京都大学大学院情報学研究科 School of Infomatics, Kyoto University |
| 第 2 著者 氏名（和/英） | 伊藤 大雄 / Hiro ITO |
| 第 2 著者 所属（和/英） | 京都大学大学院情報学研究科 School of Infomatics, Kyoto University |
| 第 3 著者 氏名（和/英） | 岩間 一雄 / Kazuo IWAMA |
| 第 3 著者 所属（和/英） | 京都大学大学院情報学研究科 School of Infomatics, Kyoto University |
| 発表年月日 | 2004/4/15 |
| 資料番号 | COMP2004-5 |
| 巻番号（vol） | vol.104 |
| 号番号（no） | 16 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |