.png){kind=icon}
.png){kind=icon}
Return
A near-real-time reduction-based algorithm for coloring massive graphs
.png){kind=icon}
PRE
AI
C
Y
DOI：10.1016/j.cor.2025.107378.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
The graph coloring problem is a classical combinatorial optimization problem with important applications such as register allocation and task scheduling, and it has been extensively studied for decades. However, near-real-time algorithms that can deliver high-quality solutions for very large real-world graphs within a strict time frame remain relatively underexplored. In this paper, we address this gap by developing an practical framework that integrates reduction rules, including degree, domination, complement crown, and independent set reductions. Building on this framework, we propose RECOL, a reduction-based algorithm that alternates between fast estimation of lower and upper bounds, graph reductions, and heuristic coloring. We evaluate RECOL on a wide range of benchmark datasets, including SNAP, the Network Repository, DIMACS10, and DIMACS2. Experimental results demonstrate that RECOL consistently outperforms state-of-the-art algorithms on three major benchmark sets of very large, sparse graphs (SNAP, the Network Repository, and DIMACS10) within one-minute time limit. Additional experiments further highlight the pivotal role of reduction techniques in achieving this performance.
Journal
C
IF:
4.3
Papers:
6.5K
Citations:
1.8W
Organization
No organization information available
Cited Papers