From Cliques to Colorings and Back Again
From Cliques to Colorings and Back Again
复制标题
DOI：
10.4230/lipics.cp.2022.26
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Marijn J. H. Heule;A. Karahalios;W. V. Hoeve
中科院分区：
文献类型：
--
作者：
Marijn J. H. Heule;A. Karahalios;W. V. Hoeve
基于可满足性技术，提出了一种求解图着色和最大团问题的精确算法。它依赖于四个子算法，交替计算较大尺寸的团和具有较少颜色的着色。我们展示了这些技术如何相互帮助：较大的集团有助于找到较小的着色，这反过来又可以促进找到较大的集团。我们评估我们的方法上的DIMACS图着色套件。对于寻找最大团，我们表明，我们的算法可以改善最先进的基于MaxSAT的求解器IncMaxCLQ
We present an exact algorithm for graph coloring and maximum clique problems based on SAT technology. It relies on four sub-algorithms that alternatingly compute cliques of larger size and colorings with fewer colors. We show how these techniques can mutually help each other: larger cliques facilitate finding smaller colorings, which in turn can boost finding larger cliques. We evaluate our approach on the DIMACS graph coloring suite. For finding maximum cliques, we show that our algorithm can improve the state-of-the-art MaxSAT-based solver IncMaxCLQ