| Presentation | 2010-12-03 Maximum Domination Problem Eiji MIYANO, Hirotaka ONO, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | We consider new variants of the vertex/edge domination problems on graphs. A vertex is said to dominate itself and its all adjacent vertices, and similarly an edge is said to dominate itself and its all adjacent edges. Given an input graph G=(V,E) and an integer k, the k-VERTEX (k-EDGE) MAXIMUM DOMINATION (k-MaxVD and k-MaxED, respectively) is to find a subset D_V⫅V of vertices (resp., D_E⫅E of edges) with size at most k that maximizes the cardinality of dominated vertices (resp., edges). In this paper, we first show that a simple greedy strategy achieves an approximation ratio of (1-1/e) for both k-MaxVD and k-MaxED. Then, we show that this approximation ratio is the best possible for k-MaxVD unless P=NP. We also prove that, for any constant ε >0, there is no polynomial time 1303/1304+ε approximation algorithm for k-MaxED unless P=NP. However, if k is not larger than the size of the minimum maximal matching, k-MaxED is 3/4-approximable in polynomial time. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | maximum domination / vertex domination / edge domination / approximability / inapproximability |
| Paper # | COMP2010-46 |
| Date of Issue |
| Conference Information | |
| Committee | COMP |
|---|---|
| Conference Date | 2010/11/26(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) | Maximum Domination Problem |
| Sub Title (in English) | |
| Keyword(1) | maximum domination |
| Keyword(2) | vertex domination |
| Keyword(3) | edge domination |
| Keyword(4) | approximability |
| Keyword(5) | inapproximability |
| 1st Author's Name | Eiji MIYANO |
| 1st Author's Affiliation | Department of Systems Design and Informatics, Faculty of Computer Science and Systems Engineering, Kyushu Institute of Technology() |
| 2nd Author's Name | Hirotaka ONO |
| 2nd Author's Affiliation | Department of Economical Engineering, Faculty of Economics, Kyushu University |
| Date | 2010-12-03 |
| Paper # | COMP2010-46 |
| Volume (vol) | vol.110 |
| Number (no) | 325 |
| Page | pp.pp.- |
| #Pages | 8 |
| Date of Issue | |