کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6904362 1446998 2018 10 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Minimum sum coloring for large graphs with extraction and backward expansion search
ترجمه فارسی عنوان
حداقل مقدار رنگ برای نمودارهای بزرگ با جستجوی استخراج و جستجوی عقب
کلمات کلیدی
مشکلات رنگ آمیزی، جستجوی ترکیبی مجموعه مستقل، کاهش مشکل،
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نرم افزارهای علوم کامپیوتر
چکیده انگلیسی
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
نویسندگان
, , , ,