کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6904362 | 1446998 | 2018 | 10 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Minimum sum coloring for large graphs with extraction and backward expansion search
ترجمه فارسی عنوان
حداقل مقدار رنگ برای نمودارهای بزرگ با جستجوی استخراج و جستجوی عقب
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
مشکلات رنگ آمیزی، جستجوی ترکیبی مجموعه مستقل، کاهش مشکل،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نرم افزارهای علوم کامپیوتر
چکیده انگلیسی
The Minimum Sum Coloring Problem (MSCP) is a relevant model tightly related to the classical vertex coloring problem (VCP). MSCP is known to be NP-hard, thus solving the problem for large graphs is particular challenging. Based on the general “reduce-and-solve” principle and inspired by the work for the VCP, we present an extraction and backward expansion search approach (EBES) to compute the upper and lower bounds for the MSCP on large graphs. The extraction phase reduces the given graph by extracting large collections of pairwise disjoint large independent sets (or color classes). The backward extension phase adds the extracted independent sets to recover the intermediate graphs while optimizing the sum coloring of each intermediate graph. We assess the proposed approach on a set of 35 large benchmark graphs with 450-4000 vertices from the DIMACS and COLOR graph coloring competitions. Computational results show that EBES is able to find improved upper bounds for 19 graphs and improved lower bounds for 12 graphs.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Applied Soft Computing - Volume 62, January 2018, Pages 1056-1065
Journal: Applied Soft Computing - Volume 62, January 2018, Pages 1056-1065
نویسندگان
Qinghua Wu, Qing Zhou, Yan Jin, Jin-Kao Hao,