کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
419083 | 681741 | 2014 | 13 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
A branch-and-cut algorithm for the equitable coloring problem using a formulation by representatives
ترجمه فارسی عنوان
الگوریتم شاخه ای و برش برای مشکل رنگ آمیزی عادلانه با استفاده از فرمول بندی توسط نمایندگان
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
An equitable kk-coloring of a graph is defined by a partition of its vertices into kk disjoint stable subsets, such that the difference between the cardinalities of any two subsets is at most one. The equitable coloring problem consists of finding the minimum value of kk such that a given graph can be equitably kk-colored. We present two new integer programming formulations based on representatives for the equitable coloring problem. We propose a primal constructive heuristic, branching strategies, and the first branch-and-cut algorithm in the literature of the equitable coloring problem. The computational experiments were carried out on randomly generated graphs, DIMACS graphs, and other graphs from the literature.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 164, Part 1, 19 February 2014, Pages 34–46
Journal: Discrete Applied Mathematics - Volume 164, Part 1, 19 February 2014, Pages 34–46
نویسندگان
Laura Bahiense, Yuri Frota, Thiago F. Noronha, Celso C. Ribeiro,