Abstract

Given an undirected graph, the Vertex Coloring Problem (VCP) consists of assigning a color to each vertex of the graph such that two adjacent vertices do not share the same color and the total number of colors is minimized. DSATUR-based Branch-and-Bound is a well-known exact algorithm for the VCP. One of its main drawbacks is that a lower bound (equal to the size of a maximal clique) is computed once at the root of the branching scheme and it is never updated during the execution of the algorithm. In this article, we show how to update the lower bound and we compare the efficiency of several lower bounding techniques

چکیده

با توجه به گراف بدون جهت، مسئله رنگ آمیزی رأس (VCP) عبارت از اختصاص رنگ به هر یک از رئوس گراف است به طوری که دو راس مجاور رنگ مشابهی را نداشته باشند و تعداد کل رنگ ها مینیمم شود. شاخه و کران مبتنی بر DSATUR یک الگوریتم دقیق شناخته شده برای VCP است. یکی از نقاط ضعف اصلی این روش این است که یک کران پایین (برابر سایز حداکثر باند) یک بار در ریشه این رویه انشعاب محاسبه شده و هرگز در طول اجرای الگوریتم آپدیت نمی شود. در این مقاله، نشان می دهیم که چگونه کران پایین را آپدیت کنیم و کارایی چندین تکنیک کران پایین را مقایسه می کنیم.

1-مقدمه

مسئله رنگ آمیزی رأس (VCP) یکی از مسائل اساسی در نظریه گراف با کاربرد در بسیاری از حوزه ها، از جمله: برنامه ریزی، جدول زمانی، ثبت تخصیص، تخصیص فرکانس، شبکه های ارتباطی و بسیاری دیگر است. با توجه به گراف بدون جهت G=(V,E) با | V | راس و | E | یال، مجموعه باثبات G، یک زیر مجموعه از رئوس غیر متصل شده و یک خوشه (دسته) از G، یک زیر مجموعه از رئوس به طور کامل متصل است...