Record Details

Approximation algorithms for the achromatic number

DSpace at IIT Bombay

View Archive Info
 
 
Field Value
 
Title Approximation algorithms for the achromatic number
 
Creator CHAUDHARY, A
VISHWANATHAN, S
 
Subject graphs
achromatic number
approximation algorithms
np-completeness
graph algorithms
 
Description The achromatic number for a graph G = dropV,E drop is the largest integer m such that there is a partition of V into disjoint independent sets {V-1,. . . , V-m} such that for each pair of distinct sets V-i,V-J,V- V-i boolean OR V-j is not an independent set in G. Yannakakis and Gavril (1980, SIAM J. Appl. Math. 38, 364-372) proved that determining this value for general graphs is NP-complete. For n-vertex graphs we present the first o(n) approximation algorithm for this problem. We also present an O(n(5/12)) approximation algorithm for graphs with girth at least 5 and a constant approximation algorithm for trees. (C) 2001 Elsevier Science.
 
Publisher ACADEMIC PRESS INC
 
Date 2011-07-12T12:11:02Z
2011-12-26T12:48:52Z
2011-12-27T05:34:21Z
2011-07-12T12:11:02Z
2011-12-26T12:48:52Z
2011-12-27T05:34:21Z
2001
 
Type Article
 
Identifier JOURNAL OF ALGORITHMS, 41(2), 404-416
0196-6774
http://dx.doi.org/10.1006/jagm.2001.1192
http://dspace.library.iitb.ac.in/xmlui/handle/10054/3321
http://hdl.handle.net/10054/3321
 
Language en