Радиораскраска в планарных графах: различия между версиями

Другая вариация алгоритма радиораскраски для планарных графов под названием «раскраска на расстоянии 2» была рассмотрена в [ ]. Задача заключается в раскраске графа G минимальным количеством цветов таким образом, чтобы вершины на расстоянии не больше 2 были раскрашены в разные цвета. Отметим, что эта задача эквивалентна задаче раскраски квадрата графа G – G2. В [11] было доказано, что задача раскраски на расстоянии 2 для планарных графов является 34 T-полной. В [5 , 6] было показано, что эта задача отличается от задачи поиска минимального порядка диапазона для радиораскраски графа. Таким образом, из доказательства NP-полноты в [ ] не следует 34 T-полнота задачи поиска минимального порядка диапазона для радиораскраски графа, доказанная в [5, 6]. В [12] также был предложен алгоритм аппроксимации с коэффициентом 9 для раскраски на расстоянии 2 для планарных графов.

Независимо и параллельно в своей работе [ ] Агнарссон и Хальдорссон представили алгоритмы аппроксимации для нахождения хроматического числа в квадратах графов и в графах более высоких степеней (Gk). В частности, они предложили алгоритм аппроксимации с коэффициентом 1:8 для раскраски квадрата планарного графа более высокой степени (A(G) > 749). Их метод использует понятие индуктивности квадрата планарного графа.

Бодлендер и коллеги [ ], также независимо и параллельно, доказали, что задача нахождения минимального диапазона для радиораскраски, которой они дали название Я-разметки, является NP-полной для планарных графов, используя подход, близкий к описанному в [5, 6]. В той же работе авторы представили алгоритмы аппроксимации для решения этой задачи для некоторых интересных семейств графов: внешнепланарных графов, графов с ограниченной древесной шириной, перестановочных и расщепляемых графов.