그래프 색칠 문제(GCP)는 NP-난해 문제이며 DSATUR는 가장 빠른 휴리스틱 중 하나지만 최신 알고리즘보다 더 많은 색을 쓰는 경향이 있다. 연구진은 이를 개선하기 위해 준정부호 계획법(SDP)으로 좋은 첫 색 클래스를 미리 계산한 뒤 DSATUR가 나머지를 색칠하도록 하는 SSLD(Semidefinite Spectral Learning with DSATUR)를 제안했다. 이 SDP는 로바스 세타 수 계산에 쓰이는 것과 유사한 방식이며, 고정된 색 클래스로 DSATUR를 개선한 것은 이번이 처음이다. DIMACS 인스턴스, 무작위 그래프, 주파수 할당, 잡숍 스케줄링 등 1,600개 이상의 벤치마크에서 SSLD는 거의 모든 경우 DSATUR와 대등하거나 더 나은 성능을 보였고 단순 1-색 클래스 전처리 기법도 능가했다. 다만 이런 품질 향상에는 DSATUR보다 약 195배 느린 실행 시간이라는 대가가 따라, SDP 기반 전처리가 향후 개선의 한 방향임을 시사한다.

• •SDP로 좋은 첫 색 클래스를 미리 계산해 DSATUR 성능을 높이는 SSLD 기법 제안
• •1,600개 이상 벤치마크에서 SSLD가 거의 모든 경우 DSATUR와 동등하거나 우수
• •단순 1-색 클래스 전처리(GISD) 대비로도 SDP 기반 선택의 가치를 확인
• •성능 향상의 대가로 실행 시간이 DSATUR 대비 약 195배 증가