کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4651585 | 1632579 | 2016 | 8 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Lower Bounding Techniques for DSATUR-based Branch and Bound
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
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.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Electronic Notes in Discrete Mathematics - Volume 52, June 2016, Pages 149–156
Journal: Electronic Notes in Discrete Mathematics - Volume 52, June 2016, Pages 149–156
نویسندگان
Fabio Furini, Virginie Gabrel, Ian-Christopher Ternier,