|
Ученые записки Ереванского государственного университета, серия Физические и Математические науки, 2007, выпуск 2, страницы 53–58
(Mi uzeru362)
|
|
|
|
Informatics
Performance ratio of the generalized greedy algorithm for $q$-coloring problem
[Отклонение обобщенного жадного алгоритма для задачи $q$-раскраски]
R. O. Adamyan Yerevan State University
Аннотация:
В данной работе описан обобщенный жадный алгоритм для нахождения $q$-хроматического подграфа, где $q$–натуральное число. Доказано, что отклонение этого алгоритма от оптимального не превосходит $\dfrac{e}{e-1}$ для произвольного $q$. Показано также, что отклонение обычного жадного алгоритма от оптимального тоже не превосходит $\dfrac{e}{e-1}$. Таким образом, прежде найденная оценка $2$ для отклонения обычного жадного алгоритма не достижима.
Поступила в редакцию: 30.10.2006
Образец цитирования:
R. O. Adamyan, “Performance ratio of the generalized greedy algorithm for $q$-coloring problem”, Уч. записки ЕГУ, сер. Физика и Математика, 2007, no. 2, 53–58
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/uzeru362 https://www.mathnet.ru/rus/uzeru/y2007/i2/p53
|
Статистика просмотров: |
Страница аннотации: | 56 | PDF полного текста: | 15 | Список литературы: | 18 |
|