Araştırmacılar grafik boyama için SSLD algoritmasını optimize etmek için sundu

Araştırmacılar, SSLD (Semidefinite Spectral Learning with DSATUR) adlı yeni bir veri ön işleme yöntemini sundu, bu yöntem grafik boyama problemi (GCP) çözümünde klasik DSATUR heuristik algoritmasının verimliliğini artırıyor.

Yöntem, ilk renk sınıfını seçmek için yarı belirlenmiş programlama (SDP) kullanmasına dayanmaktadır, ardından ana algoritma çalıştırılır. Standart yaklaşımdan farklı olarak, SSLD başlangıç kenar kümesini sabitler, bu da grafik boyama kalitesini önemli ölçüde iyileştirir ve kullanılan renklerin toplam sayısını en aza indirir.

Algoritmanın etkinliği, Erdős — Rényi grafikleri, Watts — Strogatz ve Barabási — Albert grafikleri de dahil olmak üzere 1600'den fazla benchmark ile test edildi ve ayrıca frekans atama ve üretim planlama görevlerinde test edildi. Sonuçlar, SSLD'nin tüm test edilen durumlarda standart DSATUR'den daha iyi veya eşit performans gösterdiğini gösteriyor.

Yöntemin temel kısıtlaması, hesaplama karmaşıklığıdır: ön işleme süreci, algoritmanın orijinal DSATUR'den yaklaşık 195 kat daha yavaş çalışmasına neden olur. Buna rağmen, yazarlar, ilk renk sınıfının SDP yönlendirmeli seçimini kullanmanın NP-zor görevlerin daha da optimize edilmesi için umut verici bir yol olduğunu doğruladı.

ArXiv lisansı altında yayınlanan bu çalışma, klasik heuristikleri matematiksel programlama yöntemleriyle birleştiren melez yaklaşımların, karmaşık kombinatoryal sorunları çözmek için potansiyelini gösteriyor.