Pre-processing and Linear-Decomposition Algorithm to Solve the k-Colorability Problem
Pre-processing and Linear-Decomposition Algorithm to Solve the k-Colorability Problem
复制标题
DOI：
10.1007/978-3-540-24838-5_24
复制
发表时间：
2004-05
期刊：
影响因子：
--
通讯作者：
C. Lucet;F. Mendes;A. Moukrim
中科院分区：
文献类型：
--
作者：
C. Lucet;F. Mendes;A. Moukrim
We are interested in the graph coloring problem. We studied the effectiveness of some pre-processings that are specific to the k-colorability problem and that promise to reduce the size or the difficulty of the instances. We propose to apply on the reduced graph an exact method based on a linear-decomposition of the graph. We present some experiments performed on literature instances, among which DIMACS library instances.
