.png){kind=icon}
.png){kind=icon}
返回
A near-real-time reduction-based algorithm for coloring massive graphs
.png){kind=icon}
PRE
AI
DOI：10.1016/j.cor.2025.107378.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
图着色问题是一个经典的组合优化问题，具有重要的应用，例如寄存器分配和任务调度，并且几十年来一直受到广泛研究。然而，能够在严格时间限制内为非常大的现实图提供高质量解的近实时算法仍然相对较少探索。在本文中，我们通过开发一个实用的框架来填补这一空白，该框架集成了约简规则，包括度约简、支配约简、补冠约简和独立集约简。在此基础上，我们提出了RECOL算法，这是一种基于约简的算法，它交替进行下界和上界的快速估计、图约简和启发式着色。我们在广泛的基准数据集上对RECOL进行了评估，包括SNAP、Network Repository、DIMACS10和DIMACS2。实验结果表明，在三个主要的大规模稀疏图基准集（SNAP、Network Repository和DIMACS10）的一分钟时间限制内，RECOL始终优于当前最优算法。额外的实验进一步强调了约简技术在实现这一性能中的关键作用。