Naukowcy z arXiv opublikowali metodę SSLD, która poprawia szybki algorytm heurystyczny DSATUR do kolorowania grafów poprzez inteligentne preprocessing'owanie. Zamiast od razu uruchamiać DSATUR, metoda najpierw wyznacza pierwszą klasę kolorów za pomocą programowania semidefinitowego (SDP), podobnie do techniki używanej do obliczania liczby Lovásza, a dopiero potem uruchamia DSATUR na pozostałej części grafu.
Problemy kolorowania grafów są NP-trudne, ale mają praktyczne zastosowania w przydziale częstotliwości radiowych czy planowaniu harmonogramów. DSATUR zdobył reputę jednego z najszybszych heurystyk, ale jego rezultaty zwykle wymagają więcej kolorów niż najlepsze znane algorytmy. SSLD to pierwsza próba ulepszenia DSATUR właśnie przez preprocessing stałych klas kolorów - wcześniej eksperymenty z prostszym podejściem (GISD) nie były efektywne.
Testy na ponad 1600 instancjach benchmarkowych - od klasycznych zbiorów DIMACS, przez grafy losowe różnych typów (Erdosa-Renyiego, Wattsza-Strogitza, Barabásiego-Alberta) aż po rzeczywiste problemy przydziału częstotliwości i harmonogramowania - pokazały, że SSLD osiąga co najmniej takie same rezultaty jak DSATUR w niemal każdym przypadku. Kostem jest jednak znacznie wolniejsza praca - około 195 razy mniejsza prędkość niż czysty DSATUR - ale algorytm zarabia na jakości. Wyniki sugerują, że SDP-kierowany preprocessing klasy kolorów to perspektywiczny kierunek dla przyszłych ulepszeń.