The maximum acyclic matching problem
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: 2022
Tezin Dili: İngilizce
Öğrenci: CEMRE ÇELEBİ
Danışman: TINAZ EKİM
Açık Arşiv Koleksiyonu: AVESİS Açık Erişim Koleksiyonu
Özet:Bu tezin amacı, doymuş düğümlerin herhangi bir döngü içermeyen indüklenmiş alt çizgelerinin olduğu Azami Eşleştirme anlamına gelen Azami Döngüsel Eşleştirmeyi bulmaktır. Azami Eşleştirme Problemi, mümkün olan en büyük eşleştirme kümesini bulmaya çalışır. Kombinatoryal algoritma ile çözülebilen literatürde sıklıkla rastlanan bir problemdir. Bununla birlikte, azami döngüsüz eşleştirme problemi için, sadece azami eşleştirmeyi değil, aynı zamanda doymuş düğümlerin indüklenmiş alt çizgelerinin herhangi bir döngüye sahip olmamasını istiyoruz. Bu amaçla, döngüsüzlük kısıtına ihtiyaç vardır. Belirli çizge sınıfları için oluşturulmuş bazı kesin ve yaklaşık algoritmalar olmasına rağmen, genel çizgeler için azami döngüsüz eşleştirmeyi bulan bir algoritma yoktur. Bu çalışmada dört algoritma oluşturulmuştur. Farklı yoğunluk seviyelerine ve boyutlara sahip rastgele oluşturulmuş çizgeler, bunların performanslarını analiz etmek için kullanılır. Algoritmalardan ikisi, Kompakt ve Ayrıştırma formülasyonları olan kesin algoritmalardır. Bunların verimliliğine bağlı olarak, Ayrıştırma daha iyi performans sergilemiştir. Diğer iki algoritma ise Modifikasyon ve Konstrüksiyon yaklaşımı olan buluşsal yöntemlerdir. Hem optimale yaklaşma hem de zaman verimliliği açısından Konstrüksiyon yaklaşımının Modifikasyon yaklaşımından daha iyi performans gösterdiği gözlemlenmiştir. Kesin ve buluşsal yöntemlerin en iyileri karşılaştırıldığında Ayrıştırma formülasyonu optimallik yönünden en iyi performansı göstermiştir ancak büyük boyuta sahip çizgeler için uygulanabilir değildir. Konstrüksiyon yaklaşımı daha kısa zamanda optimala yakın makul sonuçlar verir. Ayrıca çizge boyutu ve yoğunluğu büyüdükçe döngüsüzlük kısıtının etkisinin arttığı görülmektedir.