Annotation

Annotation: Various planning and resource allocation problems can be reduced to the graph coloring problem. In particular, graph coloring is used in high-level synthesis of digital circuits. The exact solution for graph coloring is not always practically achievable. For this reason, heuristic graph coloring algorithms, which allow to obtain a feasible solution with polynomial computational complexity, are of interest. Such algorithms can be used, in particular, in the problem of fast design space exploration in high-level synthesis of digital system. In this regard, the Ershov-Kozhukhin family of heuristic algorithms, which has been so far unmentioned in the modern literature on analysis of graph coloring algorithms, is of interest. A brief description and pseudocode of the Ershov-Kozhukhin algorithms is given and their experimental evaluation in comparison to the Welsh-Powell, RLF and DSATUR algorithms is presented in the paper. The evaluation shows that the Ershov-Kozhukhin algorithms have an advantage in the quality of the generated solutions compared to popular heuristic graph coloring algorithms.