| Presentation | 2006-03-22 A polynomial time algorithm for finding a minimum weighted maximal independent set in weighted chordal graph Ryosuke KONDO, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | Finding a minimum weighted maximal independent set is one of the most popular problem in graph theory. It is known that this problem is NP-hard for an arbitrary graph. Furthermore this problem is NP-hard in chordal graph. But there is a linear-time algorithm for finding a minimum weighted maximal independent set in chordal graph when the weight of each vertex is zero or one. This algorithm put the problem into the framework of linear programming. In this paper we will present a polynomial time algorithm to find a minimum weighted maximal independent set in a chordal graph with 0, 1, 2 vertex weights. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | Chordal Graph / Independent Set / Maximal Independent Set / Minimum Weighted Maximal Independent Set / Perfect Elimination Scheme |
| Paper # | COMP2005-57 |
| Date of Issue |
| Conference Information | |
| Committee | COMP |
|---|---|
| Conference Date | 2006/3/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 | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | A polynomial time algorithm for finding a minimum weighted maximal independent set in weighted chordal graph |
| Sub Title (in English) | |
| Keyword(1) | Chordal Graph |
| Keyword(2) | Independent Set |
| Keyword(3) | Maximal Independent Set |
| Keyword(4) | Minimum Weighted Maximal Independent Set |
| Keyword(5) | Perfect Elimination Scheme |
| 1st Author's Name | Ryosuke KONDO |
| 1st Author's Affiliation | Department of Mathematical and Computing Sciences Tokyo Institute of Technology() |
| Date | 2006-03-22 |
| Paper # | COMP2005-57 |
| Volume (vol) | vol.105 |
| Number (no) | 679 |
| Page | pp.pp.- |
| #Pages | 8 |
| Date of Issue | |