کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
420807 683986 2008 17 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Coloring graphs by iterated local search traversing feasible and infeasible solutions
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Coloring graphs by iterated local search traversing feasible and infeasible solutions
چکیده انگلیسی

Graph coloring is one of the hardest combinatorial optimization problems for which a wide variety of algorithms has been proposed over the last 30 years. The problem is as follows: given a graph one has to assign a label to each vertex such that no monochromatic edge appears and the number of different labels used is minimized. In this paper we present a new heuristic for this problem which works with two different functionalities. One is defined by two greedy subroutines, the former being a greedy constructive one and the other a greedy modification one. The other functionality is a perturbation subroutine, which can produce also infeasible colorings, and the ability is then to retrieve feasible solutions. In our experimentation the proper tuning of this optimization scheme produced good results on known graph coloring benchmarks.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 156, Issue 2, 15 January 2008, Pages 201–217
نویسندگان
, ,