Contemporary Methods for Graph Coloring as an Example of Discrete Optimization
The following paper provides an insight into application of the contemporary heuristic methods to graph coloring problem. Variety of algorithmic solutions for the Graph Coloring Problem (GCP) are discussed and recommendations for their implementation provided. The GCP is the NP-hard problem, aiming...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Polish Academy of Sciences
2019-06-01
|
| Series: | International Journal of Electronics and Telecommunications |
| Subjects: | |
| Online Access: | https://journals.pan.pl/Content/110219/PDF/32.pdf |
| _version_ | 1818489199376990208 |
|---|---|
| author | Adrian Bilski |
| author_facet | Adrian Bilski |
| author_sort | Adrian Bilski |
| collection | DOAJ |
| description | The following paper provides an insight into application of the contemporary heuristic methods to graph coloring problem. Variety of algorithmic solutions for the Graph Coloring Problem (GCP) are discussed and recommendations for their implementation provided. The GCP is the NP-hard problem, aiming at finding the minimum number of colors for vertices in such a way that none of two adjacent vertices are marked with the same color. With the advent of modern processing units metaheuristic approaches to solve GCP were extended to discrete optimization here. To explain the phenomenon of these methods, a thorough survey of AI-based algorithms for GCP is provided, with the main differences between specific techniques pointed out. |
| first_indexed | 2024-12-10T17:01:12Z |
| format | Article |
| id | doaj.art-1ddaf2af9a1d4359b1b0c96603b65728 |
| institution | Directory Open Access Journal |
| issn | 2081-8491 2300-1933 |
| language | English |
| last_indexed | 2024-12-10T17:01:12Z |
| publishDate | 2019-06-01 |
| publisher | Polish Academy of Sciences |
| record_format | Article |
| series | International Journal of Electronics and Telecommunications |
| spelling | doaj.art-1ddaf2af9a1d4359b1b0c96603b657282022-12-22T01:40:34ZengPolish Academy of SciencesInternational Journal of Electronics and Telecommunications2081-84912300-19332019-06-01vol. 65No 2235243https://doi.org/10.24425/ijet.2019.126306Contemporary Methods for Graph Coloring as an Example of Discrete OptimizationAdrian BilskiThe following paper provides an insight into application of the contemporary heuristic methods to graph coloring problem. Variety of algorithmic solutions for the Graph Coloring Problem (GCP) are discussed and recommendations for their implementation provided. The GCP is the NP-hard problem, aiming at finding the minimum number of colors for vertices in such a way that none of two adjacent vertices are marked with the same color. With the advent of modern processing units metaheuristic approaches to solve GCP were extended to discrete optimization here. To explain the phenomenon of these methods, a thorough survey of AI-based algorithms for GCP is provided, with the main differences between specific techniques pointed out.https://journals.pan.pl/Content/110219/PDF/32.pdfgraph coloringchromatic numbermetaheuristics |
| spellingShingle | Adrian Bilski Contemporary Methods for Graph Coloring as an Example of Discrete Optimization International Journal of Electronics and Telecommunications graph coloring chromatic number metaheuristics |
| title | Contemporary Methods for Graph Coloring as an Example of Discrete Optimization |
| title_full | Contemporary Methods for Graph Coloring as an Example of Discrete Optimization |
| title_fullStr | Contemporary Methods for Graph Coloring as an Example of Discrete Optimization |
| title_full_unstemmed | Contemporary Methods for Graph Coloring as an Example of Discrete Optimization |
| title_short | Contemporary Methods for Graph Coloring as an Example of Discrete Optimization |
| title_sort | contemporary methods for graph coloring as an example of discrete optimization |
| topic | graph coloring chromatic number metaheuristics |
| url | https://journals.pan.pl/Content/110219/PDF/32.pdf |
| work_keys_str_mv | AT adrianbilski contemporarymethodsforgraphcoloringasanexampleofdiscreteoptimization |