دانلود مقاله ISI انگلیسی شماره 79347
عنوان فارسی مقاله

یک الگوریتم ابتکاری موثر برای رنگ آمیزی حاصل جمع نمودار

کد مقاله سال انتشار مقاله انگلیسی ترجمه فارسی تعداد کلمات
79347 2012 8 صفحه PDF سفارش دهید محاسبه نشده
خرید مقاله
پس از پرداخت، فوراً می توانید مقاله را دانلود فرمایید.
عنوان انگلیسی
An effective heuristic algorithm for sum coloring of graphs
منبع

Publisher : Elsevier - Science Direct (الزویر - ساینس دایرکت)

Journal : Computers & Operations Research, Volume 39, Issue 7, July 2012, Pages 1593–1600

کلمات کلیدی
رنگ آمیزی مجموع؛ رنگ آمیزی ورتکس؛ مجموعه مستقل؛ ابتکارات
پیش نمایش مقاله
پیش نمایش مقاله یک الگوریتم ابتکاری موثر برای رنگ آمیزی حاصل جمع نمودار

چکیده انگلیسی

Given an undirected graph G=(V,E)G=(V,E), the minimum sum coloring problem (MSCP) is to find a legal vertex coloring of G  , using colors represented by natural numbers (1,2,…)(1,2,…) such that the total sum of the colors assigned to the vertices is minimized. In this paper, we present EXSCOL, a heuristic algorithm based on independent set extraction for this NP-hard problem. EXSCOL identifies iteratively collections of disjoint independent sets of equal size and assign to each independent set the smallest available color. For the purpose of computing large independent sets, EXSCOL employs a tabu search based heuristic. Experimental evaluations on a collection of 52 DIMACS and COLOR2 benchmark graphs show that the proposed approach achieves highly competitive results. For more than half of the graphs used in the literature, our approach improves the current best known upper bounds.

خرید مقاله
پس از پرداخت، فوراً می توانید مقاله را دانلود فرمایید.