کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
474163 698846 2008 16 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A graph coloring heuristic using partial solutions and a reactive tabu scheme
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر علوم کامپیوتر (عمومی)
پیش نمایش صفحه اول مقاله
A graph coloring heuristic using partial solutions and a reactive tabu scheme
چکیده انگلیسی

Most of the recent heuristics for the graph coloring problem start from an infeasible k-coloring (adjacent vertices may have the same color) and try to make the solution feasible through a sequence of color exchanges. In contrast, our approach (called FOO-PARTIALCOL), which is based on tabu search, considers feasible but partial solutions and tries to increase the size of the current partial solution. A solution consists of k disjoint stable sets (and, therefore, is a feasible, partial k-coloring) and a set of uncolored vertices. We introduce a reactive tabu tenure which substantially enhances the performance of both our heuristic as well as the classical tabu algorithm (called TABUCOL) proposed by Hertz and de Werra [Using tabu search techniques for graph coloring, Computing 1987;39:345–51]. We will report numerical results on different benchmark graphs and we will observe that FOO-PARTIALCOL, though very simple, outperforms TABUCOL on some instances, provides very competitive results on a set of benchmark graphs which are known to be difficult, and outperforms the best-known methods on the graph flat300_28_0. For this graph, FOO-PARTIALCOL finds an optimal coloring with 28 colors. The best coloring achieved to date uses 31 colors. Algorithms very close to TABUCOL are still used as intensification procedures in the best coloring methods, which are evolutionary heuristics. FOO-PARTIALCOL could then be a powerful alternative. In conclusion FOO-PARTIALCOL is one of the most efficient simple local search coloring methods yet available.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computers & Operations Research - Volume 35, Issue 3, March 2008, Pages 960–975
نویسندگان
, ,