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.
Language: English
Published: 2002
Online Access: http://ezproxy.villanova.edu/login?url=https://digital.library.villanova.edu/Item/vudl:175632