The minimum color sum of bipartite graphs

Amotz Bar-Noy, Guy Kortsarz

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


The problem of minimum color sum of a graph is to color the vertices of the graph such that the sum (average) of all assigned colors is minimum. Recently, in [BBH+96], it was shown that in general graphs this problem cannot be approximated within n1-є, for any є > 0, unless NP = ZPP. In the same paper, a 9/8-approximation algorithm was presented for bipartite graphs. The hardness question for this problem on bipartite graphs was left open. In this paper we show that the minimum color sum problem for bipartite graphs admits no polynomial approximation scheme, unless P = NP. The proof is by L-reducing the problem of finding the maximum independent set in a graph whose maximum degree is four to this problem. This result indicates clearly that the minimum color sum problem is much harder than the traditional coloring problem which is trivially solvable in bipartite graphs. As for the approximation ratio, we make a further step towards finding the precise threshold. We present a polynomial 10/9-approximation algorithm. Our algorithm uses a flow procedure in addition to the maximum independent set procedure used in previous results.

اللغة الأصليةالإنجليزيّة
عنوان منشور المضيفAutomata, Languages and Programming - 24th International Colloquium, ICALP 1997, Proceedings
المحررونPierpaolo Degano, Roberto Gorrieri, Alberto Marchetti-Spaccamela
ناشرSpringer Verlag
عدد الصفحات11
رقم المعيار الدولي للكتب (المطبوع)3540631658, 9783540631651
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 1997
الحدث24th International Colloquium on Automata, Languages and Programming, ICALP 1997 - Bologna, إيطاليا
المدة: ٧ يوليو ١٩٩٧١١ يوليو ١٩٩٧

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

الاسمLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
مستوى الصوت1256
رقم المعيار الدولي للدوريات (المطبوع)0302-9743
رقم المعيار الدولي للدوريات (الإلكتروني)1611-3349


!!Conference24th International Colloquium on Automata, Languages and Programming, ICALP 1997


أدرس بدقة موضوعات البحث “The minimum color sum of bipartite graphs'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا