| Presentation | 2000/6/19 COMP2000-15 On Approximability of the Independent/Connected Edge Dominating Set Problems Toshihiro Fujito, |
|---|---|
| PDF Download Page | PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | We investigate polynomial-time approximability of the problems related to edge dominating sets of graphs. When edges are uniformly weighted, approximating the edge dominating set problem is polynomially equivalent to approximating the minimum maximal matching problem, and for the former problem it was recently found possible to do within a factor of 2 even with arbitrary weights. It will be shown, in contrast with this, that the minimum weight maximal matching problem cannot be approximated within any polynomially computable factor unless P=NP. The connected edge dominating set problem and the connected vertex cover problem also have the same approximability when edges/vertices are unit-weighted, and the former problem is known to be approximable, even with general edge weight, within a factor of 3.598. We will show that, when general weights are allowed, 1)the connected edge dominating set problem can be approximated within a factor of 3+ε, and 2)the connected vertex cover problem is approximable within a factor of 3+1n n but cannot be within(1-ε)1n n unless NP ⊂ DTIME(n^<Ο(log log n)>). |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | edge dominating set / minimum maximal matching / connected vertex cover / approximation algorithm |
| Paper # | COMP2000-15 |
| Date of Issue |
| Conference Information | |
| Committee | COMP |
|---|---|
| Conference Date | 2000/6/19(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) | COMP2000-15 On Approximability of the Independent/Connected Edge Dominating Set Problems |
| Sub Title (in English) | |
| Keyword(1) | edge dominating set |
| Keyword(2) | minimum maximal matching |
| Keyword(3) | connected vertex cover |
| Keyword(4) | approximation algorithm |
| 1st Author's Name | Toshihiro Fujito |
| 1st Author's Affiliation | Department of Electronics Nagoya University() |
| Date | 2000/6/19 |
| Paper # | COMP2000-15 |
| Volume (vol) | vol.100 |
| Number (no) | 144 |
| Page | pp.pp.- |
| #Pages | 8 |
| Date of Issue | |