An Effective Algorithm for Edge Coloring: Malatya Edge Coloring Algorithm

Abstract

In this research, an algorithm offering effective and robust solutions for the edge coloring problem in graph theory is proposed. The edge coloring problem is identified as an NP-hard problem, known for its extensive resolution time and inability to be resolved within polynomial time. The proposed edge coloring algorithm emerges as an efficient greedy method that delivers effective solutions within polynomial time constraints. This developed algorithm employs Malatya centrality values as a decisive factor in the edge coloring process. The Malatya centrality algorithm, a current centrality method, has achieved successful outcomes in various graph problems in the literature. In this study, the algorithm is named the Malatya Edge Coloring Algorithm (MECA). To highlight the success of MECA, its analytical proof has been computationally verified on well-known graphs. Additionally, MECA has been tested on 40 unweighted and undirected lattices, 36 bipartite, 24 multipartite, 8 random, and social network graphs. The results obtained indicate that MECA provides optimal solutions for lattice, bipartite, and complete multipartite graphs while offering optimal or near-optimal solutions for any multipartite, random, and social networks. These findings emphasize the applicability and solution efficiency of the edge coloring problem in various scenarios within graph theory.

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.