Record Details

A (2+epsilon)-approximation scheme for minimum domination on circle graphs

DSpace at IIT Bombay

View Archive Info
 
 
Field Value
 
Title A (2+epsilon)-approximation scheme for minimum domination on circle graphs
 
Creator DAMIAN-IORDACHE, M
PEMMARAJU, SV
 
Subject approximation algorithms
combinatorial
approximation algorithms
circle graphs
dominating sets
 
Description The main result of this paper is a (2 + epsilon)-approximation scheme for the minimum dominating set problem on circle graphs. We first present an O(n(2)) time 8-approximation algorithm for this problem and then extend it to an O(n(3) + 6/epsilonn([6/epsilon+1])m) time (2 + epsilon)-approximation scheme for this problem. 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 + epsilon)-approximation schemes for the minimum connected and the minimum total dominating set problems on circle graphs. Keil (1993, Discrete Appl. Math. 42, 51-63) shows that these problems are NP-complete for circle graphs and leaves open the problem of devising approximation algorithms for them. These are the first O(1)-approximation algorithms for domination problems on circle graphs. .
 
Publisher ACADEMIC PRESS INC ELSEVIER SCIENCE
 
Date 2011-07-12T13:28:18Z
2011-12-26T12:48:54Z
2011-12-27T05:34:25Z
2011-07-12T13:28:18Z
2011-12-26T12:48:54Z
2011-12-27T05:34:25Z
2002
 
Type Article
 
Identifier JOURNAL OF ALGORITHMS, 42(2), 255-276
0196-6774
http://dx.doi.org/10.1006/jagm.2001.1206
http://dspace.library.iitb.ac.in/xmlui/handle/10054/3338
http://hdl.handle.net/10054/3338
 
Language en