A (2 + ε)-Approximation Scheme for Minimum Domination on Circle Graphs
✍ Scribed by Mirela Damian-Iordache; Sriram V. Pemmaraju
- Publisher
- Elsevier Science
- Year
- 2002
- Tongue
- English
- Weight
- 249 KB
- Volume
- 42
- Category
- Article
- ISSN
- 0196-6774
No coin nor oath required. For personal study only.
✦ Synopsis
The main result of this paper is a (2 + ε)-approximation scheme for the minimum dominating set problem on circle graphs. We first present an O n 2 time 8-approximation algorithm for this problem and then extend it to an O n 3 + 6 ε n 6 ε +1 m time (2 + ε)-approximation scheme for this problem. Here n and m are the number of vertices and the number of edges of the circle graph. We then present simple modifications to this algorithm that yield (3 + ε)-approximation schemes for the minimum connected and the minimum total dominating set problems on circle graphs. Keil (1993, Discrete Appl. Math. 42, 51-63) shows that these problems are NP-complete for circle graphs and leaves open the problem of devising approximation algorithms for them. These are the first O(1)-approximation algorithms for domination problems on circle graphs. 2002 Elsevier Science (USA)