PERFORMANCE RATIO OF THE GENERALIZED GREEDY ALGORITHM FOR $q$-COLORING PROBLEM
DOI:
https://doi.org/10.46991/PYSU:A/2007.41.2.053Keywords:
performance ratio, greedy algorithm, natural numberAbstract
In this paper a generalized greedy algorithm finding q-colorable subgraph is described, where q is a natural number, and it is proven that the performance ratio of the described algorithm does not exceed $e/(e-1)$ for arbitrary q. Then it is shown that the of the simple greedy algorithm also doesn't exceed $e/(e-1)$ . Thus, it follows that the performance ratio 2 previously found for simple greedy algorithm is not attainable.
Downloads
Published
2007-06-15
How to Cite
Adamyan, P. O. (2007). PERFORMANCE RATIO OF THE GENERALIZED GREEDY ALGORITHM FOR $q$-COLORING PROBLEM. Proceedings of the YSU A: Physical and Mathematical Sciences, 41(2 (213), 53–58. https://doi.org/10.46991/PYSU:A/2007.41.2.053
Issue
Section
Informatics
License
Copyright (c) 2007 Proceedings of the YSU
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.