| Presentation | 2004/4/15 Enumerating Isolated Subgraphs Tsuyoshi OSUMI, Hiro ITO, Kazuo IWAMA, |
|---|---|
| PDF Download Page | PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | 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. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | graph / Web / enumeration / clique / cut |
| Paper # | COMP2004-5 |
| Date of Issue |
| Conference Information | |
| Committee | COMP |
|---|---|
| Conference Date | 2004/4/15(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Theoretical Foundations of Computing (COMP) |
|---|---|
| Language | ENG |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Enumerating Isolated Subgraphs |
| Sub Title (in English) | |
| Keyword(1) | graph |
| Keyword(2) | Web |
| Keyword(3) | enumeration |
| Keyword(4) | clique |
| Keyword(5) | cut |
| 1st Author's Name | Tsuyoshi OSUMI |
| 1st Author's Affiliation | School of Infomatics, Kyoto University() |
| 2nd Author's Name | Hiro ITO |
| 2nd Author's Affiliation | School of Infomatics, Kyoto University |
| 3rd Author's Name | Kazuo IWAMA |
| 3rd Author's Affiliation | School of Infomatics, Kyoto University |
| Date | 2004/4/15 |
| Paper # | COMP2004-5 |
| Volume (vol) | vol.104 |
| Number (no) | 16 |
| Page | pp.pp.- |
| #Pages | 6 |
| Date of Issue | |