COMPARATIVE ANALYSIS OF COLORING ALGORITHMS FOR ORDINARY WEIGHTED GRAPH
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 fi...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | Russian |
| Published: |
Don State Technical University
2014-06-01
|
| Series: | Advanced Engineering Research |
| Subjects: | |
| Online Access: | https://www.vestnik-donstu.ru/jour/article/view/322 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849408841931816960 |
|---|---|
| author | Andrey Sergeyevich Merzlenko Valery Grigoryevich Kobak |
| author_facet | Andrey Sergeyevich Merzlenko Valery Grigoryevich Kobak |
| author_sort | Andrey Sergeyevich Merzlenko |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-dad00a7192a0456b9f10d65df12f8041 |
| institution | Kabale University |
| issn | 2687-1653 |
| language | Russian |
| publishDate | 2014-06-01 |
| publisher | Don State Technical University |
| record_format | Article |
| series | Advanced Engineering Research |
| spelling | doaj-art-dad00a7192a0456b9f10d65df12f80412025-08-20T03:35:40ZrusDon State Technical UniversityAdvanced Engineering Research2687-16532014-06-0114216417010.12737/4546315COMPARATIVE ANALYSIS OF COLORING ALGORITHMS FOR ORDINARY WEIGHTED GRAPHAndrey Sergeyevich Merzlenko0Valery Grigoryevich Kobak1Don State Technical University, RussiaDon State Technical University, RussiaAlgorithms 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.https://www.vestnik-donstu.ru/jour/article/view/322weighted graphs, weighted graph coloring, scheduling theory. |
| spellingShingle | Andrey Sergeyevich Merzlenko Valery Grigoryevich Kobak COMPARATIVE ANALYSIS OF COLORING ALGORITHMS FOR ORDINARY WEIGHTED GRAPH Advanced Engineering Research weighted graphs, weighted graph coloring, scheduling theory. |
| title | COMPARATIVE ANALYSIS OF COLORING ALGORITHMS FOR ORDINARY WEIGHTED GRAPH |
| title_full | COMPARATIVE ANALYSIS OF COLORING ALGORITHMS FOR ORDINARY WEIGHTED GRAPH |
| title_fullStr | COMPARATIVE ANALYSIS OF COLORING ALGORITHMS FOR ORDINARY WEIGHTED GRAPH |
| title_full_unstemmed | COMPARATIVE ANALYSIS OF COLORING ALGORITHMS FOR ORDINARY WEIGHTED GRAPH |
| title_short | COMPARATIVE ANALYSIS OF COLORING ALGORITHMS FOR ORDINARY WEIGHTED GRAPH |
| title_sort | comparative analysis of coloring algorithms for ordinary weighted graph |
| topic | weighted graphs, weighted graph coloring, scheduling theory. |
| url | https://www.vestnik-donstu.ru/jour/article/view/322 |
| work_keys_str_mv | AT andreysergeyevichmerzlenko comparativeanalysisofcoloringalgorithmsforordinaryweightedgraph AT valerygrigoryevichkobak comparativeanalysisofcoloringalgorithmsforordinaryweightedgraph |