A decomposition approach to solve the selective graph coloring problem

---

Tezin Türü: Doktora

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: 2018

Tezin Dili: İngilizce

Öğrenci: OYLUM ŞEKER

Danışman: TINAZ EKİM

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

Özet:

Çizge boyama problemi, bir çizgedeki tüm köşeleri birbirine komşu iki köşe aynı rengi almayacak şekilde boyama problemidir. Seçmeli çizge boyama problemi ise bilinen çizge boyama probleminin genelleştirilmiş bir hâlidir; bir çizge ve onun köşelerinin oluşturduğu kümenin bir bölmelemesi verilmişken, her bölmeden yalnızca bir tane köşeyi, sonuçta gerekecek renk sayısı en az olacak şekilde seçme problemidir. Bu çalışma, seçmeli çizge boyama problemi için ayrıştırmaya dayalı bir çözüm yöntemini, önce birtakım özel çizge sınıflarına ve daha sonra da belirli bir yapıya sahip olmayan genel çizgelere uygulamayı amaçlamaktadır. Çalışmanın ele aldığı özel çizge sınıfları, kusursuz çizge sınıfı ve onun devşirim çizgeleri, genelleştirilmiş iki parçalı çizgeler ve ki-rişli çizgelerden oluşan özel altsınıflarıdır. Kullanılan ayrıştırma yönteminin başarımını sınayabilmek için bu çizge sınıflarından somut örneklere duyulan gereksinim, çalışmanın ikinci kısmının ele alınan çizge sınıflarından rastgele örnek üretmek için yöntemler geliştirmeye odaklanmasını sağlamıştır. Ardından, ayrıştırma yöntemi, çalışmanın i-kinci kısmında üretilen farklı boyut ve yoğunluktaki çizge örnekleri üzerinde sınanmış ve sonuçlar, bir tamsayı programlama modelinin CPLEX ile çözdürülmesinden ve li-teratürde bilinen en iyi yöntemden elde edilen sonuçlarla karşılaştırılmıştır. Yapılan deneylerin sonucu göstermiştir ki ayrıştırma yöntemimiz, çözüm bulmadaki başarımı, devşirim ve genelleştirilmiş iki parçalı çizge sınıflarında özellikle düşük yoğunluklu çizgelerde, kirişli çizgelerde ise yoğunluktan bağımsız olarak önemli ölçüde geliştirmiştir. Kusursuz çizgelerin genel biçiminde yapılan deneylerde ise ayrıştırma yönteminin, karşılaştırma yapılan diğer iki yönteme de genel olarak üstün sonuçlar sağladığı görülmüştür. Öte yandan, genel çizgelerde, ayrıştırma yönteminin karşılaştırılan yöntemlerle rekabet edebilir hale gelmesi için daha fazla geliştirilmesi gerektiği görülmüştür.