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

Другая вариация алгоритма радиораскраски для планарных графов под названием ''раскраска на расстоянии 2'' была рассмотрена в [12]. Задача заключается в раскраске графа G минимальным количеством цветов таким образом, чтобы вершины на расстоянии ''не больше 2'' были раскрашены в разные цвета. Отметим, что эта задача эквивалентна задаче раскраски квадрата графа <math>G – G^2 \;</math>. В [11] было доказано, что задача раскраски на расстоянии 2 для планарных графов является NP-полной. В [5, 6] было показано, что эта задача отличается от задачи поиска минимального порядка диапазона для радиораскраски графа. Таким образом, из доказательства NP-полноты в [12] не следует NP-полнота задачи поиска минимального порядка диапазона для радиораскраски графа, доказанная в [5, 6]. В [12] также был предложен алгоритм аппроксимации с коэффициентом 9 для раскраски на расстоянии 2 для планарных графов.