Kenar Renklendirme için Etkili bir Algoritma: Malatya Kenar Renklendirme Algoritması
Küçük Resim Yok
Tarih
2025
Yazarlar
Dergi Başlığı
Dergi ISSN
Cilt Başlığı
Yayıncı
Erişim Hakkı
info:eu-repo/semantics/openAccess
Özet
Bu çalışmada çizge teorisinde kenar renklendirme problemi için etkili ve sağlam çözümler sunan bir algoritma önerilmektedir. Kenar renklendirme problemi, çözüm süresinin uzunluğu ve polinomsal zamanda çözülememesi ile bilinen NP-zor bir problem olarak tanımlanmaktadır. Önerilen kenar renklendirme algoritması, polinomsal zaman kısıtları içinde etkili çözümler sunan verimli bir açgözlü (greedy) yöntem olarak ortaya çıkmaktadır. Geliştirilen bu algoritma, kenar renklendirme sürecinde belirleyici bir faktör olarak Malatya merkezilik (centrality) değerlerini kullanmaktadır. Güncel bir merkezilik yöntemi olan Malatya merkezilik algoritması, literatürde çeşitli çizge problemlerinde başarılı sonuçlar elde etmiştir. Bu çalışmada, algoritma Malatya Kenar Renklendirme Algoritması (MECA) olarak adlandırılmıştır. MECA’nın başarısını vurgulamak amacıyla, analitik kanıtları iyi bilinen grafikler üzerinde hesaplamalı olarak doğrulanmıştır. Ayrıca, MECA; 40 ağırlıksız ve yönsüz örgü (lattice) çizge, 36 iki parçalı (bipartite), 24 çok parçalı (multipartite), 8 rastgele ve sosyal ağ çizge üzerinde test edilmiştir. Elde edilen sonuçlar, MECA’nın örgü, iki parçalı ve tam çok parçalı çizgeler için optimal çözümler sağladığını, çok parçalı, rastgele ve sosyal ağ grafiklerinde ise optimal veya optimal’e yakın çözümler sunduğunu göstermektedir. Bu bulgular, MECA’nın çizge teorisi bağlamında çeşitli senaryolarda kenar renklendirme probleminin uygulanabilirliği ve çözüm etkinliği açısından önemli bir katkı sunduğunu vurgulamaktadır.
Açıklama
Anahtar Kelimeler
Bilgisayar Bilimleri, Teori ve Metotlar
Kaynak
Turkish Journal of Science & Technology
WoS Q Değeri
Scopus Q Değeri
Cilt
20
Sayı
1
