| Presentation | 2020-03-01 On Approximation Algorithms for Power Vertex Cover Problem Takumi Tatematsu, Tetsuro Rintani, Toshihiro Fujito, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | We present two 2-approximation algorithms for Power Vertex Cover problem, which is a generalization ofthe Vertex Cover problem. Given in Power Vertex Cover is a graph G = (V,E) with “edge” weights w(e), and an edge e = {u, v} is covered only if power p ∈ R ^V_+ assigned on the vertices satisfy either p(u) ? w(e) or p(v) ? w(e). We aim to find a power assignment of minimum sum that covers all edges in G. Clearly, Vertex Cover corresponds to Power Vertex Cover when all edge weights are equal to 1. In this paper, we present two 2-approximation algorithms for this problem, one designed based on LP rounding and the other based on the local ratio theorem. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | Vertex Cover Problem / Graph Theory / Approximation Algorithms |
| Paper # | COMP2019-50 |
| Date of Issue | 2020-02-23 (COMP) |
| Conference Information | |
| Committee | COMP |
|---|---|
| Conference Date | 2020/3/1(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | The University of Electro-Communications |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | Toshihiro Fujito(Toyohashi Univ. of Tech.) |
| Vice Chair | Shinichi Nakano(Gunma Univ.) |
| Secretary | Shinichi Nakano(Kumamoto Univ) |
| Assistant | Kazuhisa Seto(Seikei Univ.) |
| Paper Information | |
| Registration To | Technical Committee on Theoretical Foundations of Computing |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | On Approximation Algorithms for Power Vertex Cover Problem |
| Sub Title (in English) | |
| Keyword(1) | Vertex Cover Problem |
| Keyword(2) | Graph Theory |
| Keyword(3) | Approximation Algorithms |
| 1st Author's Name | Takumi Tatematsu |
| 1st Author's Affiliation | Toyohashi University of Technology(TUT) |
| 2nd Author's Name | Tetsuro Rintani |
| 2nd Author's Affiliation | Toyohashi University of Technology(TUT) |
| 3rd Author's Name | Toshihiro Fujito |
| 3rd Author's Affiliation | Toyohashi University of Technology(TUT) |
| Date | 2020-03-01 |
| Paper # | COMP2019-50 |
| Volume (vol) | vol.119 |
| Number (no) | COMP-433 |
| Page | pp.pp.29-33(COMP), |
| #Pages | 5 |
| Date of Issue | 2020-02-23 (COMP) |