Record Details

Constant-factor approximation algorithms for domination problems on circle graphs

DSpace at IIT Bombay

View Archive Info
 
 
Field Value
 
Title Constant-factor approximation algorithms for domination problems on circle graphs
 
Creator DAMIAN-IORDACHE, M
PEMMARAJU, SV
 
Description A graph G = (V, E) is called a circle graph if there is a one- to-one 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 is an element of V either u is an element of 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), 51-63) shows that the minimum dominating set problem (MDS), the minimum connected dominating set problem (MCDS) and the minimum total domination problem (MTDS) are all NP-complete 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 approximating minimum independent dominating set on circle graphs (Damian-Iordache and Pemmaraju, in this proceedings) advance our understanding of domination problems on circle graphs significantly.
 
Publisher SPRINGER-VERLAG BERLIN
 
Date 2011-10-23T12:53:44Z
2011-12-15T09:11:09Z
2011-10-23T12:53:44Z
2011-12-15T09:11:09Z
2000
 
Type Article; Proceedings Paper
 
Identifier ALGORITHMS AND COMPUTATIONS,1741,70-82
3-540-66916-7
0302-9743
http://dspace.library.iitb.ac.in/xmlui/handle/10054/15134
http://hdl.handle.net/100/1889
 
Source 10th Annual International Symposium on Algorithms and Computation (ISAAC 99),CHENNAI, INDIA,DEC 16-18, 1999
 
Language English