图着色问题（GCP）是 NP 难问题，DSATUR 作为最快的启发式算法之一，虽然速度快，却往往使用比最先进算法更多的颜色。我们提出 SSLD（Semidefinite Spectral Learning with DSATUR），通过在 DSATUR 完成其余节点着色之前，先预处理得到一个质量较高的颜色类来提升 DSATUR。该颜色类来源于半正定规划（SDP），其形式与用于计算 Lovász θ 数的 SDP 类似。
据我们所知，SSLD 是首个通过固定颜色类进行预处理来改进 DSATUR 的方法。我们在 DIMACS 基准、随机图（Erdős‑Rényi、Watts‑Strogatz、Barabási‑Albert）、频率分配以及作业车间调度实例上进行评估。
实验结果显示，SSLD 在超过 1600 个基准实例中几乎全部匹配或超越 DSATUR，并且显著优于朴素的 1‑颜色类预处理基线 GISD，验证了 SDP 引导的首个颜色类选择的价值。该提升以约 195 倍的运行时间开销为代价，表明 SDP 引导的预处理是未来改进的可行方向。
点评