کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
418868 681723 2014 11 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A branch-and-price algorithm for the robust graph coloring problem
ترجمه فارسی عنوان
الگوریتم شاخه و قیمت برای رفع مشکل رنگ آمیزی درست نمودار
کلمات کلیدی
رنگ آمیزی نمودار، راهکار مناسب، الگوریتم شاخه و قیمت، جستجوی تابو
فهرست مطالب مقاله
چکیده

کلمات کلیدی

1.مقدمه

شکل 1. تصویری از رنگ آمیزی درست و بهینه

2.تعریف مشکل

3.الگوریتم شاخه و قیمت

3.1مشکل قیمت گذاری

3.2قوانین شاخه بندی

3.3راهکار مشکل قیمت گذاری

3.4تولید ستون

4.آزمایش های محاسباتی

الگوریتم 1: الگوریتم تولید ستون برای راه حل LMP

جدول 1.نتایج برای اولین مجموعه از نمونه ها

جدول 2. نتایج مجموعه ی دوم نمونه ها

شکل 2. زمان محاسبه برای مقدایر مختلف k

جدول 3. شاخصه های عملکرد

5.نتیجه گیری
ترجمه چکیده
با توجه به نمودار G، عدد صحیح k، و هزینه یCuv مرتبط با تمامی جفت های uv در رئوس غیرمجاور در G، مشکل رنگ آمیزی درست نمودار با هدف تخصیص یک رنگ در {1، ......K} برای هر راس G است تا هیچ کرانه ای دو نقطه ی پایانی با یک رنگ مشابه نداشته باشد و هزینه ی کل جفت ها به کمترین میزان برسد. الگوریتم قیمت و شاخه را برای حل این مشکل پیشنهاد می دهیم. مشکل قیمت گذاری شامل یافتن مجموعه ای ثابت برای حداقل مقدار کل است و الگوریتم های اکتشافی و استخراجی را به عنوان راهکار ارائه می دهیم. آزمایش های محاسباتی هم برای نمونه های رنگ آمیزی نمودار تولید شده به طور تصادفی و معیار گزارش می شوند.
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش مقاله
الگوریتم شاخه و قیمت برای رفع مشکل رنگ آمیزی درست نمودار
چکیده انگلیسی

Given a graph GG, an integer kk, and a cost cuvcuv associated with all pairs uvuv of non-adjacent vertices in GG, the robust graph coloring problem is to assign a color in {1,…,k}{1,…,k} to every vertex of GG so that no edge has both endpoints with the same color, and the total cost of the pairs of vertices having the same color is minimum. We propose a branch-and-price algorithm for the solution of this problem. The pricing problem consists in finding a stable set of minimum total weight, and we propose both an exact and a heuristic algorithm for its solution. Computational experiments are reported for randomly generated and benchmark graph coloring instances.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 165, 11 March 2014, Pages 49–59
نویسندگان
, , ,