海量图着色算法

一分钟内高质量着色

RECOL结合归约规则与启发式着色，针对超大规模稀疏图在一分钟时限内稳定求解。

Chenghao, Zhu · Zhou, Yi

Computers and Operations Research 2026

参数信息

时间限制

1 min

技术优势

不用反复调参

RECOL 在上下界估计、图归约和启发式着色之间交替进行，自动缩小搜索范围，用户无需为每个图手动调整参数。

不牺牲解的质量

归约规则先简化图结构而不改变最优目标值，使启发式着色能在更小的图上找到与原图等价的解，从而在短时间内保持高质量。

应用场景

• 任务调度：在严格时限内为大规模任务分配资源，避免冲突并提高执行效率。
• 寄存器分配：快速为编译器中的变量分配寄存器，减少溢出，提升程序运行速度。
• 大规模图数据处理：对超大规模稀疏图进行实时着色，支持数据分析中的图划分与模式发现。