Simple decentralized graph coloring

详细信息    查看全文

• 作者：Severino F. Galán
• 关键词：Graph coloring problem ; Simple decentralized approach ; Conflicting edges minimization ; Graph coloring quality
• 刊名：Computational Optimization and Applications
• 出版年：2017
• 出版时间：January 2017
• 年：2017
• 卷：66
• 期：1
• 页码：163-185
• 全文大小：
• 刊物类别：Mathematics and Statistics
• 刊物主题：Optimization; Operations Research, Management Science; Operation Research/Decision Theory; Statistics, general; Convex and Discrete Geometry;
• 出版者：Springer US
• ISSN：1573-2894
• 卷排序：66

文摘

Graph coloring is a classical NP-hard combinatorial optimization problem with many practical applications. A broad range of heuristic methods exist for tackling the graph coloring problem: from fast greedy algorithms to more time-consuming metaheuristics. Although the latter produce better results in terms of minimizing the number of colors, the former are widely employed due to their simplicity. These heuristic methods are centralized since they operate by using complete knowledge of the graph. However, in real-world environmets where each component only interacts with a limited number of other components, the only option is to apply decentralized methods. This paper explores a novel and simple algorithm for decentralized graph coloring that uses a fixed number of colors and iteratively reduces the edge conflicts in the graph. We experimentally demonstrate that, for most of the tested instances, the new algorithm outperforms a recent and very competitive algorithm for decentralized graph coloring in terms of coloring quality. In our experiments, the fixed number of colors used by the new algorithm is controlled in a centralized manner.