ConstantFactor Approximation Algorithms for Domination Problems on Circle Graphs.
A graph G = (V,E) is called a circle graph if there is a onetoone correspondence between vertices in V and a set C of chords in a circle such that two vertices in V are adjacent if and only if the corresponding chords in C intersect. A subset V' of V is a dominating set of G if for all u E V is either u E V' or u has a neighbor in V'. In addition, if G[V'] is connected, then V' is called a connected dominating set; if G[V'] has no isolated vertices, then V' is called a total dominating set. Keil (Discrete Applied Mathematics, 42 (1993), 5163) shows that the minimum dominating set problem (MDS), the minimum connected dominating set problem (MCDS) and the minimum total domination problem (MTDS) are all NPcomplete even for circle graphs. He mentions designing approximation algorithms for these problems as being open. This paper presents O(1)approximation algorithms for all three problems  MDS, MCDS, and MTDS on circle graphs. For any circle graph with n vertices and m edges, these algorithms take O(n^2+nm) time and O(n^2) space. These results, along with the result on the hardness of approximate minimum independent dominating set on circle graphs (DamianIordache and Pemmaraju, in this proceedings) advance our understanding of domination problems on circle graphs significantly.
Main Author:  DamianIordache, Mirela. 

Other Authors:  Pemmaraju, Sriram V. 
Language:  English 
Published: 
1999

Online Access: 
http://ezproxy.villanova.edu/login?url=https://digital.library.villanova.edu/Item/vudl:175656 