An improved approximation of the achromatic number on bipartite graphs

Research output: Contribution to journalArticle

2 Citations (Scopus)

Abstract

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].

Original languageEnglish (US)
Pages (from-to)361-373
Number of pages13
JournalSIAM Journal on Discrete Mathematics
Volume21
Issue number2
DOIs
StatePublished - Dec 1 2007

Fingerprint

Achromatic number
Bipartite Graph
Subset
Approximation
Greedy Algorithm
Best Approximation
Partition
Distinct
Graph in graph theory

All Science Journal Classification (ASJC) codes

  • Mathematics(all)

Cite this

@article{bfd0fe991be5490182ef3d073693f903,
title = "An improved approximation of the achromatic number on bipartite graphs",
abstract = "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].",
author = "Guy Kortsarz and Sunil Shende",
year = "2007",
month = "12",
day = "1",
doi = "10.1137/S0895480104442947",
language = "English (US)",
volume = "21",
pages = "361--373",
journal = "SIAM Journal on Discrete Mathematics",
issn = "0895-4801",
publisher = "Society for Industrial and Applied Mathematics Publications",
number = "2",

}

An improved approximation of the achromatic number on bipartite graphs. / Kortsarz, Guy; Shende, Sunil.

In: SIAM Journal on Discrete Mathematics, Vol. 21, No. 2, 01.12.2007, p. 361-373.

Research output: Contribution to journalArticle

TY - JOUR

T1 - An improved approximation of the achromatic number on bipartite graphs

AU - Kortsarz, Guy

AU - Shende, Sunil

PY - 2007/12/1

Y1 - 2007/12/1

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].

UR - http://www.scopus.com/inward/record.url?scp=45249092315&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=45249092315&partnerID=8YFLogxK

U2 - 10.1137/S0895480104442947

DO - 10.1137/S0895480104442947

M3 - Article

AN - SCOPUS:45249092315

VL - 21

SP - 361

EP - 373

JO - SIAM Journal on Discrete Mathematics

JF - SIAM Journal on Discrete Mathematics

SN - 0895-4801

IS - 2

ER -