Algorithms of solving the “minimax” weighted graph coloring problem are considered and compared. The mathematical formulation of the problem is presented; the solution optimality criteria are stated. The exact algorithm that always finds the minimum count of colors through Maghout method and then finds the “minimax” option using 3 versions of the critical path method is described. Three fast heuristic algorithms are described: the algorithm that works with the list of vertexes arranged by the local degrees; the algorithm based on the removal of the points and adjacent edges; the algorithm using the vertex saturation rate. All algorithms are considered with examples. To evaluate the algorithm efficiency, a computational experiment on several hundred of randomly generated graphs is set up. The algorithms were compared by the operating speed and the proximity of the result to the "minimax" version of coloring.
Рассматриваются и сравниваются алгоритмы решения задачи поиска «минимаксной» раскраски взвешенного по вершинам графа. Приведена математическая постановка задачи, указаны критерии оптимальности решения. Описан точный алгоритм, всегда находящий минимальные по количеству цветов раскраски методом Магу и затем отыскивающий среди них «минимаксный» вариант с помощью 3 модификаций алгоритма «критического пути». Описаны три быстрых эвристических алгоритма: алгоритм, работающий с упорядоченным по локальным степеням списком вершин; алгоритм, основанный на удалении вершин и смежных рёбер; алгоритм, использующий степень насыщения вершин. Все алгоритмы рассмотрены с примерами. Для оценки эффективности алгоритмов поставлен вычислительный эксперимент на нескольких сотнях случайно сгенерированных графов. Алгоритмы сравнивались по скорости работы и близости результата к «минимаксному» варианту раскраски.
The authors declare that there are no conflicts of interest present.