Solving dynamic graph coloring problem by using a heuristic algorithm

Abstract

Grafik renklendirme problemi literatürdeki en popüler optimizationproblemlerinden biridir. Problemin grafiklerle modellenebilen bir çok gerçek problemeuygulunabilmesi, grafik renklendirme problemini önemli kılmaktadır. Probleminpolinom zamanda henüz bir çözümünün bulunamaması, bu problem için bir çok sezgiselalgoritmanın geliştirilmesine sebep olmuştur. Ancak geliştirilen bu sezgisel algoritmalardinamik grafiklerdeki renklendirme problemlerine uyum sağlayamamıştır.Dinamik grafiklerdeki renklendirme problemi dinamik grafik renklendirmeproblemi olarak adlandırılmış ve bir kaç senedir üzerinde çalışmalar yapılmayabaşlanmıştır. Bu sebeple, literatürde bu yeni keşfedilen problem için az sayıda sezgiselalgoritma bulunmaktadır.Bu çalışmada, dinamik grafik renklendirme problemini çözmek amacıyla birevrimsel algoritma geliştirilmiştir. Algoritma belirlenen bir zaman aralığında değişendinamik grafikleri dikkate almaktadır ve bu değişimlere kolayca uyumsağlayabilmektedir. Algoritma literatürde yer alan ve dinamik grafik renklendirmeproblemi için geliştirilen iki sezgisel algoritma ile birlikte çeşitli senaryolara sahip bir çokdinamik grafik üzerinde test edilmiştir ve bu çalışmada sunulan algoritmanın bir çokdurumda diğer algoritmalardan daha iyi sonuçlar elde ettiği görülmüştür.

Graph coloring problem is one of the most popular optimization problem in theliterature. The problem can be applied to solve many real-world problems that aremodeled by using graphs. Since graph coloring problem is an NP-hard problem, there aremany heuristic algorithms to solve the problem in different domains. However, theseheuristic solutions are for solving static graphs and they are hard to be adapted in dynamicgraphs.Graph coloring problem in dynamic graphs is called dynamic graph coloringproblem and this problem has been explored for the last few years. Therefore, there areonly a few and recently proposed heuristic algorithms to solve the dynamic graph coloringproblem in the literature.In this study, we propose an evolutionary algorithm for solving dynamic graphcoloring problem. The algorithm considers dynamic graphs changing over a givennumber of time steps. It adapts to the changes in the graph with its novel pool-basedcrossover operator easily. We tested our algorithm with two heuristic methods fordynamic graph coloring problem in the literature on dynamic graphs which have differentcharacteristics and compared the solutions of the algorithms. The results show that ouralgorithm outperforms these two algorithms in most of the test cases given.