DSATUR
A classical graph coloring heuristic proposed by Daniel Brélaz in 1979, based on a greedy strategy with dynamic vertex ordering by saturation degree. Its time complexity is O(n²); it is computationally efficient but lacks a backtracking mechanism and can converge to locally suboptimal solutions on dense graphs.
Timeline (last 90 days)
The DSATUR algorithm was proposed by Daniel Brélaz in 1979.
DSATUR dynamically selects the coloring order based on vertex saturation (the number of distinct colors used by adjacent vertices), breaking ties by choosing the vertex with the highest degree, with a time complexity of O(n²).
The coloring solutions produced by DSATUR tend to use more colors than state-of-the-art coloring algorithms, and on dense graphs or adversarial structures it easily falls into local suboptima with no backtracking mechanism.
SSLD (Semidefinite Spectral Learning with DSATUR) is a new method proposed in a paper posted on arXiv (arXiv:2609.17633) that pre-seeds a high-quality first color class using semidefinite programming before DSATUR begins, and then hands off the remaining vertex coloring to DSATUR.
The authors state that, to their knowledge, SSLD is the first method to improve DSATUR by preprocessing with a fixed color class.
SSLD matches or surpasses DSATUR's coloring quality in nearly all settings, while also clearly outperforming the naive GISD baseline (single color-class preprocessing without SDP guidance).
SSLD's running time is approximately 195 times that of DSATUR.
If coloring quality is a hard constraint and computation time is relatively flexible, SSLD is worth using; if maximum speed is the priority, the original DSATUR is the more pragmatic choice.
SSLD embodies the idea of combining continuous optimization (SDP/spectral methods) with discrete heuristics: using SDP to capture the global graph structure, then using DSATUR for fast local decisions.
All Facts (9)
SSLD embodies the idea of combining continuous optimization (SDP/spectral methods) with discrete heuristics: using SDP to capture the global graph structure, then using DSATUR for fast local decisions.
50%UnverifiedDSATUR dynamically selects the coloring order based on vertex saturation (the number of distinct colors used by adjacent vertices), breaking ties by choosing the vertex with the highest degree, with a time complexity of O(n²).
50%UnverifiedThe coloring solutions produced by DSATUR tend to use more colors than state-of-the-art coloring algorithms, and on dense graphs or adversarial structures it easily falls into local suboptima with no backtracking mechanism.
50%UnverifiedThe DSATUR algorithm was proposed by Daniel Brélaz in 1979.
50%UnverifiedThe authors state that, to their knowledge, SSLD is the first method to improve DSATUR by preprocessing with a fixed color class.
50%UnverifiedSSLD matches or surpasses DSATUR's coloring quality in nearly all settings, while also clearly outperforming the naive GISD baseline (single color-class preprocessing without SDP guidance).
50%UnverifiedSSLD's running time is approximately 195 times that of DSATUR.
50%UnverifiedIf coloring quality is a hard constraint and computation time is relatively flexible, SSLD is worth using; if maximum speed is the priority, the original DSATUR is the more pragmatic choice.
50%UnverifiedSSLD (Semidefinite Spectral Learning with DSATUR) is a new method proposed in a paper posted on arXiv (arXiv:2609.17633) that pre-seeds a high-quality first color class using semidefinite programming before DSATUR begins, and then hands off the remaining vertex coloring to DSATUR.
50%