DSATUR
由Daniel Brélaz于1979年提出的经典图着色启发式算法，基于顶点饱和度动态排序的贪心策略，时间复杂度O(n²)，速度高效但缺乏回溯机制，在稠密图上易陷入局部次优
时间轴 (近 90 天)
DSATUR算法由Daniel Brélaz于1979年提出
DSATUR依据顶点饱和度（相邻顶点已使用的不同颜色数）动态选择着色顺序，饱和度相同则选度数最大者，时间复杂度为O(n²)
DSATUR给出的着色方案所用颜色数往往多于当前最先进的着色算法，在稠密图或对抗性结构上容易陷入局部次优且无回溯机制
SSLD（Semidefinite Spectral Learning with DSATUR）是一篇发布于arXiv（arXiv:2609.17633）的论文提出的新方法，通过在DSATUR开始前用半定规划预置一个高质量的第一色类，再交由DSATUR完成剩余顶点着色
作者称据其所知SSLD是首个通过固定色类预处理来改进DSATUR的方法
SSLD在几乎所有情形下都能匹配或超越DSATUR的着色质量，同时也明显优于朴素的GISD基线（不使用SDP指导的单色类预处理）
SSLD的运行时间约为DSATUR的195倍
如果着色质量是硬约束而计算时间相对宽裕，SSLD值得使用；如果追求极致速度，原始DSATUR是更务实的选择
SSLD体现了将连续优化（SDP/谱方法）与离散启发式相结合的思路：用SDP从全局把握图结构，再用DSATUR做局部快速决策
全部知识事实 (9)
SSLD体现了将连续优化（SDP/谱方法）与离散启发式相结合的思路：用SDP从全局把握图结构，再用DSATUR做局部快速决策
50%待验证DSATUR依据顶点饱和度（相邻顶点已使用的不同颜色数）动态选择着色顺序，饱和度相同则选度数最大者，时间复杂度为O(n²)
50%待验证DSATUR给出的着色方案所用颜色数往往多于当前最先进的着色算法，在稠密图或对抗性结构上容易陷入局部次优且无回溯机制
50%待验证DSATUR算法由Daniel Brélaz于1979年提出
50%待验证作者称据其所知SSLD是首个通过固定色类预处理来改进DSATUR的方法
50%待验证SSLD在几乎所有情形下都能匹配或超越DSATUR的着色质量，同时也明显优于朴素的GISD基线（不使用SDP指导的单色类预处理）
50%待验证SSLD的运行时间约为DSATUR的195倍
50%待验证如果着色质量是硬约束而计算时间相对宽裕，SSLD值得使用；如果追求极致速度，原始DSATUR是更务实的选择
50%待验证SSLD（Semidefinite Spectral Learning with DSATUR）是一篇发布于arXiv（arXiv:2609.17633）的论文提出的新方法，通过在DSATUR开始前用半定规划预置一个高质量的第一色类，再交由DSATUR完成剩余顶点着色
50%