A (2+e)-Approximation Scheme for Minimum Domination on Circle Graphs.
The main result of this paper is a (2 + e)-approximation scheme for the minimum dominating set problem on circle graphs. We first present an O(n 2) time 8-approximation algorithm for the minimum dominating set problem on circle graphs and then extend it to a (2+e)-approximation scheme that solves the minimum dominating set problem in time O(n 3 + -6g_,f~i +l,~,~ ]. 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 dominating set and the minimum total dominating set problems on circle graphs. Keil (Discrete Applied Mathematics, 42 (1993), 51-63) showed that these problems are NP-complete for circle graphs and left open the problem of devising approximation algorithms for them. These are the first O(1)- approximation algorithms for domination problems on circle graphs and involve techniques that may lead to new approximation algorithms for other problems like vertex cover and chromatic number on circle graphs.
|Main Author:||Damian-Iordache, Mirela.|
|Other Authors:||Pemmaraju, Sriram V.|