Determining the expected runtime of exact graph coloring
Zoltán Ádám Mann, Anikó Szajkó · 2010
Exact algorithms for graph coloring tend to have high variance in their runtime, posing a significant obstacle to their practical application. The problem could be mitigated by appropriate prediction of the runtime. For this purpose, we devise an algorithm to efficiently compute the expected runtime of an exact graph coloring algorithm as a function of the graph’s size, density, and the number of available colors.