OVERVIEW OF GRAPH COLORING METHODS AND ALGORITHMS
PDF (English)

Ключові слова

vertex; graph; chromatic number; algorithms; heuristic methods; graph coloring; experiment; density; sampling
вершина; граф; хроматичне число; алгоритми; евристичні методи; розфарбовування графу; експеримент, вибірка

Як цитувати

Денисенко, О. (2019). OVERVIEW OF GRAPH COLORING METHODS AND ALGORITHMS. ΛΌГOΣ. МИСТЕЦТВО НАУКОВОЇ ДУМКИ, (7), 27-32. https://doi.org/10.36074/2617-7064.07.00.006

Анотація

The problem of graph coloring using heuristic methods was considered. The purpose of the work is to analyze heuristic methods and describe computational experiments using a program for heuristic evaluation of a chromatic number. Such methods as the greedy algorithm, the full-search method, the random-search method, and the depth-limited search method were considered. Experiments aimed at evaluating the quality of the solutions formed by different methods were conducted. Comparison of the results of the use of different methods for graphs which differ in such properties as, for example, the number of vertices and connection density, depending on search parameters of specific methods, gives us data for the analysis of the relevance of the use of these methods for the solution of specific practical problems, such as scheduling, cluster analysis, calculation of derivatives, parallelization of numerical methods, frequency distribution, digital signs, allocation of processor registers.

__________

ОГЛЯД МЕТОДІВ ТА АЛГОРИТМІВ РОЗФАРБОВУВАННЯ ГРАФУ

В роботі розглядається задача пошуку хроматичного числа евристичними методами. Ціллю даної роботи є аналіз евристичних методів та опис обчислювальних експериментів за допомогою програми для евристичної оцінки хроматичного числа. Розглянуто такі методи як жадібний алгоритм, метод повного перебору, метод випадкового перебору, а також, метод перебору з обмеженням в глибину. Проведено експерименти, з метою оцінки якості рішень, які сформовані за допомогою різних методів.

https://doi.org/10.36074/2617-7064.07.00.006
PDF (English)

Посилання

Wilson, R. J., Nikitina, I. G., & Gavrilov, G. P. (1977). Vvedenie v teorii︠u︡ grafov [Introduction to graph theory]. Moskva: Izdatelʹstvo «Mir».

Tatt, U. (1988). Teoriia grafov [Graph theory]. Moskva: Izdatelʹstvo «Mir».

Harary, F. (1973). Teoriia grafov [Graph theory]. Moskva: Izdatelʹstvo «Mir».

Berge, C., Zykov A. A. & Vajnštejn I. Ǎ. (1973). Teoriâ grafov i ee primeneniâ. Moskva: Izdatelʹstvo inostrannoj literatury.

Ore, O. (1965) Grafy i ikh primeneniie [Graphs and their use]. Moskva: Izdatelʹstvo «Mir».

Ore, O. (1980). Teoriâ grafov. Moskva: Izdatelʹstvo «Nauka», Glavnaâ redakciâ fiziko-matematičeskoj literatury.

Kristofides, N., Verškov É V., Konovalʹcev, I. V., & Gavrilov G. P. (1978). Teoriâ grafov: algoritmičeskij podhod. Moskva: Izdatelʹstvo «Mir.

Yevstigneyev, V. A. (1985). Primenenie teorii grafov v programmirovanii [The use of graph theory in rogramming]. Moskva: Izdatelʹstvo Nauka, 1985.

Berezina, L. Yu. (1979). Grafy i ikh primeneniie [Graphs and their use]. Moskva: Izdatelʹstvo Prosveshchenie

Kolyasnikov, D. V., & Vatutin, E. I. (2013). Analysis of the degree of approximation to the optimal evaluation of the chromatic number of a graph using heuristic methods. Materials from the XI-Th International Scientific Conference (p. 253–255), Kursk: Publishing house of the South-West State University.

Svami, M. (1984). Grafy seti i algoritmy [Graphs, networks, and algorithms]. Moskva: Izdatelʹstvo «Mir».

Donyets, H. A. & Shor, N. Z. (1982). Algebraicheskii podkhod k probleme raskraski ploskikh grafov [Algebraic approach to the problem of coloring flat graphs]. Kyiv: Vydavnytstvo Naukova Dumka.

Zykov, A. A. (1987). Osnovy teorii grafov [Fundamentals of the graph theory]. Moskva: Izdatelʹstvo Nauka.

Cameron, P. & J. van Lint. (1980). Teoriia grafov teoriia kodirovaniia i blok-skhemy [Graph theory, coding theory, and flowcharts]. Moskva:Izdatelʹstvo Nauka.

Maynika, E. (1981). Algoritmy optimizatsii na setiakh i grafakh [Optimization algorithms on networks and graphs]. Moskva: Izdatelʹstvo Mir.

Melikhov, A. N., Bershtein, L. S. & Kureichik, V. M. (1974). Primenenie grafov dlia proektirovaniia diskretnykh ustroistv [The use of graphs for designing discrete devices]. Moskva: Izdatelʹstvo Nauka

Melnikov, O. I. (2001). Zanimatelnye zadachi po teorii grafov [Interesting problems related to the graph heory]. Minsk: Izdatelʹstvo Tetra Systems

Harary, F., Palmer, E. (1977). Perechislenie grafov [Enumeration of graphs]. Moskva: Izdatelʹstvo Mir.

Vatutin, E. I., Dremov, Ye. N., Martynov, I. A. & Titov, V. S. (2014). Weighted random enumeration method for solving discrete combinatorial optimization problems. News of the Volgograd State Technical University. Series: Electronics, Measuring Equipment, Radio Engineering, and Communications, 10(9), 59–64.

Creative Commons License

Ця робота ліцензується відповідно до Creative Commons Attribution 4.0 International License.

Завантаження

Дані завантаження ще не доступні.

| Переглядів: 73 | Завантажень: 104 |