Open AccessAlgorithms on Graph Coloring Problem
Author(s) -
Mingtao Yang
Publication year - 2020
Publication title -
journal of physics. conference series
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.21
H-Index - 85
eISSN - 1742-6596
pISSN - 1742-6588
DOI - 10.1088/1742-6596/1634/1/012053
Subject(s) - graph coloring , greedy coloring , computer science , algorithm , fractional coloring , list coloring , complicity , greedy algorithm , graph , mathematics , theoretical computer science , graph power , line graph , political science , law
Graph coloring problem is one of the most famous NP-complete problem and it is an important problem in the study of set theory and graph theory. Since it was raised, lots of people has tried many methods to solve the problem or to optimize the solution to this problem. In this article, the author will introduce the concept of the graph coloring problem and two solutions of the problem. One is based on genetic algorithm and the other is based on greedy algorithm. Each solution has its own traits. Through the analysis, this paper aims to reduce the complicity of the algorithms for making them useful in various applications.