An exact algorithm with learning for the graph coloring problem
An exact algorithm with learning for the graph coloring problem
复制标题
图着色问题的精确学习算法
DOI：
10.1016/j.cor.2014.05.017
复制
发表时间：
2014-11-01
影响因子：
4.6
通讯作者：
Xu, Ruchu
中科院分区：
文献类型：
--
作者：
Zhou, Zhaoyang;Li, Chu-Min;Xu, Ruchu
给定一个无向图G=(V，E)，图着色问题(GCP)在于给图G的每个顶点分配一种颜色，使得任意两个相邻的顶点被赋予不同的颜色，并且所使用的不同颜色的数量最少。最新算法一般处理GCP中的显式约束：任意两个相邻顶点应该被赋予不同的颜色，但不专门处理显式约束所隐含的非相邻顶点之间的隐式约束。在本文中，我们提出了一种带学习的GCP精确算法，该算法利用命题逻辑的隐式约束。我们的算法与文献中最好的几种精确算法进行了比较。实验结果表明，该算法在很多情况下都优于其他算法。具体地说，我们的算法允许关闭由Elsevier Ltd.发布的打开的DIMACS实例4-Fullins_5。(C)2014。
Given an undirected graph G=(V,E), the Graph Coloring Problem (GCP) consists in assigning a color to each vertex of the graph G in such a way that any two adjacent vertices are assigned different colors, and the number of different colors used is minimized. State-of-the-art algorithms generally deal with the explicit constraints in GCP: any two adjacent vertices should be assigned different colors, but do not specially deal with the implicit constraints between non-adjacent vertices implied by the explicit constraints. In this paper, we propose an exact algorithm with learning for GCP which exploits the implicit constraints using propositional logic. Our algorithm is compared with several exact algorithms among the best in the literature. The experimental results show that our algorithm outperforms other algorithms on many instances. Specifically, our algorithm allows to close the open DIMACS instance 4-Fullins_5. (C) 2014 Published by Elsevier Ltd.