#半定规划

SSLD：用半定规划预处理单色类改进图着色启发式DSATUR

arXiv新论文提出SSLD方法，通过半定规划（SDP）预处理第一色类来改进经典图着色启发式DSATUR。在1600多个基准实例上SSLD匹配或超越DSATUR，代价是约195倍的运行时间，为SDP引导的图着色预处理指明新方向。