PERFORMANCE RATIO OF THE GENERALIZED GREEDY ALGORITHM FOR $q$-COLORING PROBLEM

P. O. Adamyan

doi:10.46991/PYSU:A/2007.41.2.053

PERFORMANCE RATIO OF THE GENERALIZED GREEDY ALGORITHM FOR $q$-COLORING PROBLEM

Authors

P. O. Adamyan Chair of Discrete Mathematics and Theoretical Informatics, YSU, Armenia

DOI:

https://doi.org/10.46991/PYSU:A/2007.41.2.053

Keywords:

performance ratio, greedy algorithm, natural number

Abstract

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