Preview

Advanced Engineering Research (Rostov-on-Don)

Advanced search

COMPARATIVE ANALYSIS OF COLORING ALGORITHMS FOR ORDINARY WEIGHTED GRAPH

https://doi.org/10.12737/4546

Abstract

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.

About the Authors

Andrey Sergeyevich Merzlenko
Don State Technical University, Russia
Russian Federation


Valery Grigoryevich Kobak
Don State Technical University, Russia
Russian Federation


References

1. Карп, Р. М. Сводимость комбинаторных проблем / Р. М. Карп // Кибернетический сборник, вып. 12. — Москва : Мир, 1975. — С. 16‒38.

2. Гэри, М. Вычислительные машины и труднорешаемые задачи / М. Гэри, Д. Джонсон. — Москва : Мир, 1982. — 416 с.

3. Букин, В. В. Алгоритм раскраски взвешенного графа / В. В. Букин, В. Г. Кобак // Известия СКНЦ ВШ. Техн. науки. — 1998. — №2. — С. 12‒14.

4. Кофман, А. Введение в прикладную комбинаторику / А. Кофман. — Москва : Наука, 1975. — 480 с.

5. Кобак, В. Г. Модификация алгоритма обслуживания «по критическому пути» для систем с избирательными свойствами приборов / В. Г. Кобак // Микропроцессорные и цифровые системы. — 2003. — № 2 (6). — С. 156‒162.

6. Емельянов, В. В. Теория и практика эволюционного моделирования / В. В. Емельянов, В. М. Курейчик, В. В. Курейчик. — Москва : ФИЗМАТЛИТ, 2003. — 432 с.

7. Кристофидес, Н. Теория графов. Алгоритмический подход / Н. Кристофидес. — Москва : Мир, 1988. — 432 с.

8. Койнов, Р. В. Практикум по дискретной математике / Р. В. Койнов, Л. С. Лисицына. — Санкт-Петербург : Изд-во СПбГУ ИТМО, 2004. — 78 с.

9. Евстигнеев, В. А. Применение теории графов в программировании / В. А. Евстигнеев. — Москва : Наука, 1985. — 352 с.

10. Welsh, D. J. A. An upper bound for the chromatic number of a graph and its application to timetabling problems / D. J. A. Welsh, M. B. Powell // The Computer Journal. — № 10 (1), 1967. — С. 85‒86.


Review

For citations:


Merzlenko A.S., Kobak V.G. COMPARATIVE ANALYSIS OF COLORING ALGORITHMS FOR ORDINARY WEIGHTED GRAPH. Vestnik of Don State Technical University. 2014;14(2):164-170. (In Russ.) https://doi.org/10.12737/4546

Views: 498


Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 License.


ISSN 2687-1653 (Online)