Experimental Analysis of Algorithms for the Dynamic Graph Coloring Problem

Menno Theunis¹ ; Marcel Roeloffzen¹

¹ Eindhoven University of Technology

Journal of graph algorithms and applications, Tome 28 (2024) no. 1, pp. 313-349

Résumé

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.

Détail

DOI : 10.7155/jgaa.v28i1.2956

Keywords: graph coloring, dynamic graph coloring, experimental analysis, algorithm comparison