4501
правка
Радиораскраска в планарных графах: различия между версиями
Перейти к навигации
Перейти к поиску
м
Радиораскраска в планарных графах (посмотреть исходный код)
Версия от 13:46, 12 апреля 2016
, 12 апреля 2016→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 71: | Строка 71: | ||
Независимо и параллельно в своей работе [ ] Агнарссон и Хальдорссон представили алгоритмы аппроксимации для нахождения хроматического числа в квадратах графов и в графах более высоких степеней <math>(G^k) \;</math>. В частности, они предложили алгоритм аппроксимации с коэффициентом 1,8 для раскраски квадрата планарного графа более высокой степени <math>(\Delta(G) \ge 749) \;</math>. Их метод использует понятие [[индуктивность|индуктивности]] квадрата планарного графа. | Независимо и параллельно в своей работе [1] Агнарссон и Хальдорссон представили алгоритмы аппроксимации для нахождения хроматического числа в квадратах графов и в графах более высоких степеней <math>(G^k) \;</math>. В частности, они предложили алгоритм аппроксимации с коэффициентом 1,8 для раскраски квадрата планарного графа более высокой степени <math>(\Delta(G) \ge 749) \;</math>. Их метод использует понятие [[индуктивность|индуктивности]] квадрата планарного графа. | ||
Бодлендер и коллеги [2], также независимо и параллельно, доказали, что задача нахождения минимального диапазона для радиораскраски, которой они дали название <math>\lambda</math>-разметки, является NP-полной для планарных графов, используя подход, близкий к описанному в [5, 6]. В той же работе авторы представили алгоритмы аппроксимации для решения этой задачи для некоторых интересных семейств графов: [[внешнепланарный граф|внешнепланарных]] графов, [[древесная ширина графа|графов с ограниченной древесной шириной]], [[перестановочный граф|перестановочных]] и [[расщепляемый граф|расщепляемых графов]]. | Бодлендер и коллеги [2], также независимо и параллельно, доказали, что задача нахождения минимального диапазона для радиораскраски, которой они дали название <math>\lambda</math>-разметки, является NP-полной для планарных графов, используя подход, близкий к описанному в [5, 6]. В той же работе авторы представили алгоритмы аппроксимации для решения этой задачи для некоторых интересных семейств графов: [[внешнепланарный граф|внешнепланарных]] графов, [[древесная ширина графа|графов с ограниченной древесной шириной]], [[перестановочный граф|перестановочных]] и [[расщепляемый граф|расщепляемых графов]]. | ||