| Presentation | 2009-10-16 Reformulation of the scheme for computing tree-width and minimum fill-in Masanobu FURUSE, Yota OTACHI, Koichi YAMAZAKI, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | Bouchitte and Todinca introduced a scheme, i.e., Dynamic Programming based on recursive formulas in terms of minimal separators and potential maximal cliques, that computes the tree-width and minimum fill-in of a graph G if G and a list of all minimal separators of G are given as inputs. In this paper, we extend/reformulate the scheme so that it can be used for computing other graph parameters, and demonstrate the utility of the extended scheme. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | tree-width / minimum fill-in / triangulation / maximal clique / minimal separator / potencial maximal clique |
| Paper # | COMP2009-34 |
| Date of Issue |
| Conference Information | |
| Committee | COMP |
|---|---|
| Conference Date | 2009/10/9(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 | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Reformulation of the scheme for computing tree-width and minimum fill-in |
| Sub Title (in English) | |
| Keyword(1) | tree-width |
| Keyword(2) | minimum fill-in |
| Keyword(3) | triangulation |
| Keyword(4) | maximal clique |
| Keyword(5) | minimal separator |
| Keyword(6) | potencial maximal clique |
| 1st Author's Name | Masanobu FURUSE |
| 1st Author's Affiliation | Department of Computer Science, Gunma University() |
| 2nd Author's Name | Yota OTACHI |
| 2nd Author's Affiliation | Department of Computer Science, Gunma University |
| 3rd Author's Name | Koichi YAMAZAKI |
| 3rd Author's Affiliation | Department of Computer Science, Gunma University |
| Date | 2009-10-16 |
| Paper # | COMP2009-34 |
| Volume (vol) | vol.109 |
| Number (no) | 235 |
| Page | pp.pp.- |
| #Pages | 8 |
| Date of Issue | |