TY - JOUR
T1 - Experimental Analysis of Algorithms for the Dynamic Graph Coloring Problem
AU - Theunis, Menno
AU - Roeloffzen, Marcel
N1 - Publisher Copyright:
© 2024, Brown University. All rights reserved.
PY - 2024/5/16
Y1 - 2024/5/16
N2 - This paper focuses on the dynamic graph coloring problem, a dynamic variant based on the well-researched graph coloring problem. This variant of the problem not only considers the number of colors used in the coloring for a graph, but also how many nodes in this graph need to change their color when the graph is changed. The balance between these two measures of quality, as well as running time, creates an inherent trade-off, in which algorithms solving this problem often only focus on one or the other. A variety of such algorithms already exist and are compared, as well as improved upon, in this paper. Each of these algorithms uses different variables to measure its effectiveness, making it difficult to compare their advantages and disadvantages. Finding the right option for a practical application is thus unnecessarily difficult. By implementing the different algorithms and comparing them experimentally, we get a better insight of the strong and weak points of these algorithms. Using this knowledge we propose two new improved variants of these algorithms, obtained by combining aspects of the existing ones. We find that this approach of combining existing algorithms with different strong points often yields superior results and allows for a more versatile trade-off within the algorithm, making it suitable for a broader range of practical applications.
AB - This paper focuses on the dynamic graph coloring problem, a dynamic variant based on the well-researched graph coloring problem. This variant of the problem not only considers the number of colors used in the coloring for a graph, but also how many nodes in this graph need to change their color when the graph is changed. The balance between these two measures of quality, as well as running time, creates an inherent trade-off, in which algorithms solving this problem often only focus on one or the other. A variety of such algorithms already exist and are compared, as well as improved upon, in this paper. Each of these algorithms uses different variables to measure its effectiveness, making it difficult to compare their advantages and disadvantages. Finding the right option for a practical application is thus unnecessarily difficult. By implementing the different algorithms and comparing them experimentally, we get a better insight of the strong and weak points of these algorithms. Using this knowledge we propose two new improved variants of these algorithms, obtained by combining aspects of the existing ones. We find that this approach of combining existing algorithms with different strong points often yields superior results and allows for a more versatile trade-off within the algorithm, making it suitable for a broader range of practical applications.
KW - algorithm comparison
KW - dynamic graph coloring
KW - experimental analysis
KW - graph coloring
UR - http://www.scopus.com/inward/record.url?scp=85203052148&partnerID=8YFLogxK
U2 - 10.7155/jgaa.v28i1.2956
DO - 10.7155/jgaa.v28i1.2956
M3 - Article
AN - SCOPUS:85203052148
SN - 1526-1719
VL - 28
SP - 313
EP - 349
JO - Journal of Graph Algorithms and Applications
JF - Journal of Graph Algorithms and Applications
IS - 1
ER -