Unit disk graph coloring and its reoptimization

---

Tezin Türü: Yüksek Lisans

Tezin Yürütüldüğü Kurum: Boğaziçi Üniversitesi, FEN BİLİMLERİ ENSTİTÜSÜ, FEN BİLİMLERİ ENSTİTÜSÜ, Türkiye

Tezin Onay Tarihi: 2009

Tezin Dili: İngilizce

Öğrenci: ARMAN BOYACI

Danışman: TINAZ EKİM

Açık Arşiv Koleksiyonu: AVESİS Açık Erişim Koleksiyonu

Özet:

Bir takım birim diskin Öklid düzleminde kesişimleri birim disk çizgedir(BDÇ).Özellikle telekomünikasyondaki frekans atama probleminin ¸cözümü için önemli ve NPzorproblemler olan birim disk çizge boyama(BDÇBoya) problemini ve yeniden eniyilenmesiniele aldık. Çalışmanın ilk kısmında, deneysel testler gerçekleşstirerek BDÇBoyaprobleminin alt ve üst sınırlarının kalitesi incelendi. Bazı gözlemlere dayanarak, mevcutO(n4.5) klik algoritmasının ortalama koşu zamanında iyileştirme sağlandı. Ekolarak, iki yeni boyama sezgiseli ve Kempe'nin Zincirlerinden ilham alınarak yenibir iyileştirme yöntemi önerildi. İkinci kısımda ise, köşe ekle/çıkar yeniden eniyilemeproblemleri tanımlandı. Eski örneğe ait eniyi çözüm bilgisine rağmen bu problemlerinNP-zor kaldıklarını gösterdik ve bu nedenle sezgisel yöntemler önerdik. Bu sezgisellerinortalama performansları, deneysel çalışmalar ile tayin edildi. Ayrıca Brelaz'ınardışık boyama algoritmasını köşe ekle yeniden eniyileme problemini ¸çözebilecek şekildeuyarladık.