Çizgelerde eşli baskın küme probleminin çözümünde merkeziyet temelli bir çözüm yöntemi önerme

Çizge teorisi, mühendislik uygulamalarında önemli bir role sahiptir. Birçok bilimsel ve mühendislik tabanlı problemi, ağ yapısı şeklinde modelleyerek analiz etmek ve çözmek yaygın olarak kullanılmaktadır. Öte yandan, çizge teorisindeki birçok problem NP-zor veya NP-tamamlanmış olarak sınıflandırılır ve bu nedenle polinom zamanında çözülemez. Polinom zamanında çözümler elde etmek için çeşitli yaklaşımlar önerilmiştir. Bu tez çalışmasında optimal deterministik bir algoritma önerilmektedir. Eşli baskın küme oluşumunda merkeziyet metrikleri kullanılmış; her çift için birincil lider düğümü ve onun yedek (bekleme) düğümü olarak görev yapan ikincil düğümü belirleyen bir çözüm sunulmuştur. Önerilen yöntem, çeşitli boyut ve özelliklere sahip ağlara uygulanmış ve neredeyse tüm durumlarda tam kapsama sağlanmıştır. Yani seçilen düğümlerin oluşturduğu kümenin dışında kalan her düğüm bu kümedeki en az bir elemanla komşudur. Dahası, yaklaşım, özellikle büyük ölçekli ağlar için zaman karmaşıklığı açısından verimlilik sağlamaktadır.