On approximating the achromatic number

Guy Kortsarz, Robert Krauthgamer

نتاج البحث: فصل من :كتاب / تقرير / مؤتمرمنشور من مؤتمرمراجعة النظراء


The achromatic number problem is to legally color the vertices of an input graph with the maximum number of colors, denoted &psgr;*, so that every two color classes share at least one edge. This problem is known to be NP-hard. For general graphs we give an algorithm that approximates the achromatic number within ratio of &Ogr;(n -log log n/ log n). This improves over the previously known approximation ratio of &Ogr; (n/Vlog n), due to Chaudhary and Vishwanathan [4]. For graphs of girth at least 5 we give an algorithm with approximation ratio &Ogr;(min{n1/3, V&psgr;*}). This improves over an approximation ratio &Ogr;(V&psgr;*) = &Ogr;(n3/8) for the more restricted case of graphs with girth at least 6, due to Krista and Lorys [13]. We also give the first hardness result for approximating the achromatic number. We show that for every fixed □ > 0 there in no 2 - D approximation algorithm, unless P = NP.

اللغة الأصليةالإنجليزيّة
عنوان منشور المضيفProceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms
عدد الصفحات10
حالة النشرنُشِر - 2001
الحدث2001 Operating Section Proceedings, American Gas Association - Dallas, TX, الولايات المتّحدة
المدة: ٣٠ أبريل ٢٠٠١١ مايو ٢٠٠١

سلسلة المنشورات

الاسمProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms


!!Conference2001 Operating Section Proceedings, American Gas Association
الدولة/الإقليمالولايات المتّحدة
المدينةDallas, TX


أدرس بدقة موضوعات البحث “On approximating the achromatic number'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا