%0 Book
%A Damian-Iordache, Mirela.
%E Pemmaraju, Sriram V.
%D 2002
%G English
%T A (2+e)-Approximation Scheme for Minimum Domination on Circle Graphs.
%U http://ezproxy.villanova.edu/login?url=https://digital.library.villanova.edu/Item/vudl:175632
%X 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.