Record Details

DSpace at IIT Bombay

View Archive Info
 

Metadata

 
Field Value
 
Title Constant-factor approximation algorithms for domination problems on circle graphs
 
Names DAMIAN-IORDACHE, M
PEMMARAJU, SV
Date Issued 2000 (iso8601)
Abstract 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.
Genre Article; Proceedings Paper
Identifier ALGORITHMS AND COMPUTATIONS,1741,70-82