The maximum stable set problem in perfect graphs
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: 2017
Tezin Dili: İngilizce
Öğrenci: AHMET ÇAĞRI DÜZGÜN
Danışman: TINAZ EKİM
Açık Arşiv Koleksiyonu: AVESİS Açık Erişim Koleksiyonu
Özet:En büyük kararlı küme problemi çizgeler kuramındaki iyi bilinen bir problemdir. Bu problem genel bir çizge için NP-zor bir problemdir. Teorik ve uygulamadaki öneminden dolayı fazlaca çalışılmıştır. Problemi sadece çizge sınıflarının en önemli sınıflarından biri olan mükemmel çizgeler için ele aldığımız zaman, problemin polinom zamanda yarı kesin programlamaya dayanan bir algoritma ile çözüldüğünü görürüz. Fakat yarı kesin programlama problemlerinin özellikle fazla değişkenli oldu-ğunda yavaş çözüldüğü de bilinir. Ayrıca, problemi sadece mükemmel çizgelerde inceleyen sınırlı sayıda yayın vardır. Tüm bunları göz önüne aldığımızda bizim amacımız yarı kesin programlamaya dayanan algoritma ile diğer algoritmaların performansını mükemmel çizgelerde karşılaştırmaktır. Bu amaçla biz kesen düzlem algoritmaları geliştirdik. Ayrıca, en büyük kararlı küme problemini herhangi bir çizgede çözen güçlü bir algoritma örneği görebilmek için güçlü bir dal-sınır algoritmasını inceledik ve sonra bu algoritmaları mükemmel çizge örnekleri kullanarak karşılaştırdık. Karşılaştırmaları-mız kesen düzlem algoritmalarının diğerlerinden daha iyi çalıştığını ortaya çıkardı.