Coloring Dynamic Graphs with a Similarity and Pool-Based Evolutionary Algorithm

Terci G. S., BOZ B.

IEEE Access, 2025 (SCI-Expanded) identifier

  • Yayın Türü: Makale / Tam Makale
  • Basım Tarihi: 2025
  • Doi Numarası: 10.1109/access.2025.3546108
  • Dergi Adı: IEEE Access
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus, Compendex, INSPEC, Directory of Open Access Journals
  • Anahtar Kelimeler: crossover operator, Dynamic graphs, edge-dynamic graphs, evolutionary algorithms, graph coloring problem, node-dynamic graphs
  • Marmara Üniversitesi Adresli: Evet

Özet

The graph coloring problem is a well-known optimization challenge, particularly relevant in dynamic environments where the graph undergoes continuous changes over time. Evolutionary algorithms, known for their adaptability and effectiveness in handling NP-hard problems, are well-suited for tackling the issues related to coloring dynamic graphs. In this paper, we present a novel Similarity and Pool-Based Evolutionary Algorithm designed to address the graph coloring problem on dynamic graphs. Our approach employs a partition-based representation that adapts to dynamic graph changes while preserving valuable historical information. The algorithm introduces an innovative similarity and conflict-based crossover operator aimed at minimizing the number of colors used, alongside a local search method to enhance solution diversity. We evaluated the performance of the proposed algorithm against a well-known heuristic for the graph coloring problem and a genetic algorithm with a dynamic population across a diverse set of dynamic graphs. Experimental results demonstrate that our algorithm consistently outperforms these alternatives by reducing the number of colors required in the majority of test cases.