کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
418316 681632 2014 15 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Exploring the role of graph spectra in graph coloring algorithm performance
ترجمه فارسی عنوان
بررسی نقش طیف گراف در عملکرد الگوریتم رنگ آمیزی گراف
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی

This paper considers the challenge of recognizing how the properties of a graph determine the performance of graph coloring algorithms. In particular, we examine how spectral properties of the graph make the graph coloring task easy or hard. We address the question of when an exact algorithm is likely to provide a solution in a reasonable computation time, when we are better off using a quick heuristic, and how the properties of the graph influence algorithm performance. A new methodology is introduced to visualize a collection of graphs in an instance space defined by their properties, with an optimal feature selection approach included to ensure that the instance space preserves the topology of an algorithm performance metric. In this instance space we can reveal how different algorithms perform across a variety of instance classes with various properties. We demonstrate the methodology using a sophisticated branch and bound exact algorithm, and the faster heuristic approaches of integer rounding of a linear programming relaxation of the graph coloring formulation, as well as a greedy degree-saturation heuristic. Our results demonstrate that spectral properties of the graph instances can provide useful descriptions of when each of these algorithms will provide the best solution for a given computational effort.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 176, 30 October 2014, Pages 107–121
نویسندگان
, ,