TY - JOUR
T1 - An improved approximation of the achromatic number on bipartite graphs
AU - Kortsarz, Guy
AU - Shende, Sunil
PY - 2007
Y1 - 2007
N2 - The achromatic number of a graph G = (V, E) with |V| = n vertices is the largest number k with the following property: the vertices of G can be partitioned into k independent subsets {Vi}1≤i≤k such that for every distinct pair of subsets Vi, Vj in the partition, there is at least one edge in E that connects these subsets. We describe a greedy algorithm that computes the achromatic number of a bipartite graph within a factor of O(n4/5) of the optimal. Prior to our work, the best known approximation factor for this problem was n log log n/ log n as shown by Kortsarz and Krauthgamer [SIAM J. Discrete Math., 14 (2001), pp. 408-422].
AB - The achromatic number of a graph G = (V, E) with |V| = n vertices is the largest number k with the following property: the vertices of G can be partitioned into k independent subsets {Vi}1≤i≤k such that for every distinct pair of subsets Vi, Vj in the partition, there is at least one edge in E that connects these subsets. We describe a greedy algorithm that computes the achromatic number of a bipartite graph within a factor of O(n4/5) of the optimal. Prior to our work, the best known approximation factor for this problem was n log log n/ log n as shown by Kortsarz and Krauthgamer [SIAM J. Discrete Math., 14 (2001), pp. 408-422].
KW - Approximation algorithms
KW - Coloring of graphs and hypergraphs
KW - Graph algorithms
UR - http://www.scopus.com/inward/record.url?scp=45249092315&partnerID=8YFLogxK
U2 - 10.1137/S0895480104442947
DO - 10.1137/S0895480104442947
M3 - ???researchoutput.researchoutputtypes.contributiontojournal.article???
AN - SCOPUS:45249092315
SN - 0895-4801
VL - 21
SP - 361
EP - 373
JO - SIAM Journal on Discrete Mathematics
JF - SIAM Journal on Discrete Mathematics
IS - 2
ER -