OVERVIEW OF GRAPH COLORING METHODS AND ALGORITHMS
Journal Title: ΛΌГOΣ. МИСТЕЦТВО НАУКОВОЇ ДУМКИ - Year 2019, Vol 1, Issue 7
Abstract
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. __________ ОГЛЯД МЕТОДІВ ТА АЛГОРИТМІВ РОЗФАРБОВУВАННЯ ГРАФУ В роботі розглядається задача пошуку хроматичного числа евристичними методами. Ціллю даної роботи є аналіз евристичних методів та опис обчислювальних експериментів за допомогою програми для евристичної оцінки хроматичного числа. Розглянуто такі методи як жадібний алгоритм, метод повного перебору, метод випадкового перебору, а також, метод перебору з обмеженням в глибину. Проведено експерименти, з метою оцінки якості рішень, які сформовані за допомогою різних методів.
Authors and Affiliations
Олексій Денисенко
Keywords
Related Articles
- EP ID EP665436
- DOI 10.36074/2617-7064.07.00.006
- Views 193
- Downloads 0
DEVELOPMENT OF NANOTECHNOLOGIES AND MANUFACTURE OF NANOMATERIALS IN UKRAINE
The analysis and research of the development of nanotechnologies in Ukraine is one of the most promising forms of intellectual capital. The processes and problems of the development of nanotechnologies and the manufactur...
CAUSES OF TAX EVASION
This article covers the causes of non-payment of taxes in Ukraine. What provokes the tax authorities to this and the methods of improving this situation. Varieties of taxes, their influence on the economic, financial sta...
СПЕЦИФІКА ПІДГОТОВКИ ФАХІВЦІВ У СФЕРІ «ЛАНДШАФТНА АРХІТЕКТУРА ТА ДИЗАЙН»
В статті розглянуто питання підвищення якісної освіти у ВНЗ України, зокрема підготовки спеціалістів у галузі ландшафтної архітектури та дизайну. Запропоновано шляхи активізації творчої діяльності студентів і пошук нових...
EXTENDED MODEL PUPILS’ ICT COMPETENCIES IN PRIMARY SCHOOL
In search of factors influencing the development of pupils’ ICT competencies, a number of conceptual provisions were developed and empirically confirmed in the course of the research. The proposed methods are ways of ini...
БАГАТОВИМІРНЕ ОЦІНЮВАННЯ ПРИВАБЛИВОСТІ КРАЇН СВІТУ: СТАТИСТИЧНИЙ АСПЕКТ
Досліджено доцільність прийняття інвестиційних рішень спираючись на світові рейтингові оцінки економічних процесів в країнах Світу.