✦ LIBER ✦

On Approximating the Achromatic Number

✍ Scribed by Kortsarz, Guy; Krauthgamer, Robert

Book ID: 118199520
Publisher: Society for Industrial and Applied Mathematics
Year: 2001
Tongue: English
Weight: 206 KB
Volume: 14
Category: Article
ISSN: 0895-4801
DOI: 10.1137/s0895480100379579

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

An Improved Approximation of the Achroma

An Improved Approximation of the Achromatic Number on Bipartite Graphs

✍ Kortsarz, Guy; Shende, Sunil 📂 Article 📅 2007 🏛 Society for Industrial and Applied Mathematics 🌐 English ⚖ 190 KB

Approximation Algorithms for the Achroma

Approximation Algorithms for the Achromatic Number

✍ Amitabh Chaudhary; Sundar Vishwanathan 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 108 KB

The achromatic number for a graph G = V E 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 i ∪ V j is not an independent set in G. Yannakakis and Gavril (1980, SIAM J. Appl. Math. 38, 364-372) p

Efficient approximation algorithms for t

Efficient approximation algorithms for the achromatic number

✍ Piotr Krysta; Krzysztof Loryś 📂 Article 📅 2006 🏛 Elsevier Science 🌐 English ⚖ 357 KB

Some results on the achromatic number

✍ Cairnie, Niall; Edwards, Keith 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 106 KB

Let G be a simple graph. The achromatic number ψ(G) is the largest number of colors possible in a proper vertex coloring of G in which each pair of colors is adjacent somewhere in G. For any positive integer m, let q(m) be the largest integer k such that ( k 2 ) ≤ m. We show that the problem of dete

On the Achromatic Number of Hypercubes

✍ Yuval Roichman 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 96 KB

The achromatic number of a finite graph G, (G), is the maximum number of independent sets into which the vertex set may be partitioned, so that between any two parts there is at least one edge. For an m-dimensional hypercube P m 2 we prove that there exist constants 0<c 1 <c 2 , independent of m, su

On the Hardness of Approximating the Chr

On the Hardness of Approximating the Chromatic Number

✍ Khanna, Sanjeev (author);Linial, Nathan (author);Safra, Shmuel (author) 📂 Article 📅 2000 🏛 Janos Bolyai Mathematical Society 🌐 English ⚖ 311 KB