4501
правка
Радиораскраска в планарных графах: различия между версиями
Перейти к навигации
Перейти к поиску
м
Радиораскраска в планарных графах (посмотреть исходный код)
Версия от 13:26, 1 октября 2023
, 1 октября 2023нет описания правки
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) мНет описания правки |
||
| Строка 60: | Строка 60: | ||
• Был представлен алгоритм с временем исполнения <math>O(n \Delta (G)) \;</math>, ''аппроксимирующий'' минимальный порядок радиораскраски, <math>X_{order} \;</math>, в планарном графе G ''с константным коэффициентом, который стремится к 2'' по мере возрастания максимальной степени <math>\Delta(G) \;</math> графа G. | • Был представлен алгоритм с временем исполнения <math>O(n \Delta (G)) \;</math>, ''аппроксимирующий'' минимальный порядок радиораскраски, <math>X_{order} \;</math>, в планарном графе G ''с константным коэффициентом, который стремится к 2'' по мере возрастания максимальной степени <math>\Delta(G) \;</math> графа G. | ||
Представленный алгоритм вдохновлен теоремой Хёвела и Макгиннеса о конструктивной раскраске [9]. Построение из [9], как показано, может привести к получению алгоритма с временем <math>O(n^2) \;</math>, предполагая, что планарное вложение графа G задано. В [5, 6] временная сложность алгоритма | Представленный алгоритм вдохновлен теоремой Хёвела и Макгиннеса о конструктивной раскраске [9]. Построение из [9], как показано, может привести к получению алгоритма с временем <math>O(n^2) \;</math>, предполагая, что планарное вложение графа G задано. В [5, 6] временная сложность аппроксимационного алгоритма была улучшена, также был представлен намного более простой алгоритм для проверки и внедрения, не требующий на входе планарного вложения. | ||
• Наконец, была рассмотрена задача ''оценки количества различных радиораскрасок'' планарного графа G. Это NP-полная задача (что можно легко заметить в связи с представленным в данных работах способом редукции полноты, которая может быть выполнена консервативным образом). Авторы применяют здесь стандартную технику, сочетая цепи Маркова и новый способ формирования пар, чтобы получить доказательство ''быстрой сходимости'' (см., например, [10]) и представляют ''полностью полиномиальную рандомизированную схему аппроксимации'' для оценки количества радиораскрасок с <math>\lambda \;</math> цветами для планарного графа G, когда <math>\lambda \ge 4 \Delta (G) + 50 \;</math>. | • Наконец, была рассмотрена задача ''оценки количества различных радиораскрасок'' планарного графа G. Это NP-полная задача (что можно легко заметить в связи с представленным в данных работах способом редукции полноты, которая может быть выполнена консервативным образом). Авторы применяют здесь стандартную технику, сочетая цепи Маркова и новый способ формирования пар, чтобы получить доказательство ''быстрой сходимости'' (см., например, [10]) и представляют ''полностью полиномиальную рандомизированную схему аппроксимации'' для оценки количества радиораскрасок с <math>\lambda \;</math> цветами для планарного графа G, когда <math>\lambda \ge 4 \Delta (G) + 50 \;</math>. | ||
| Строка 68: | Строка 68: | ||
Другая вариация алгоритма радиораскраски для планарных графов под названием ''раскраска на расстоянии 2'' была рассмотрена в [12]. Задача заключается в раскраске графа G минимальным количеством цветов таким образом, чтобы вершины на расстоянии ''не больше 2'' были раскрашены в разные цвета. Отметим, что эта задача эквивалентна задаче раскраски квадрата графа <math>G \; (G^2)</math>. В [11] было доказано, что задача раскраски на расстоянии 2 для планарных графов является NP-полной. В [5, 6] было показано, что эта задача отличается от задачи поиска минимального порядка диапазона для радиораскраски графа. Таким образом, из доказательства NP-полноты в [12] не следует NP-полнота задачи поиска минимального порядка диапазона для радиораскраски графа, доказанная в [5, 6]. В [12] также был предложен алгоритм | Другая вариация алгоритма радиораскраски для планарных графов под названием ''раскраска на расстоянии 2'' была рассмотрена в [12]. Задача заключается в раскраске графа G минимальным количеством цветов таким образом, чтобы вершины на расстоянии ''не больше 2'' были раскрашены в разные цвета. Отметим, что эта задача эквивалентна задаче раскраски квадрата графа <math>G \; (G^2)</math>. В [11] было доказано, что задача раскраски на расстоянии 2 для планарных графов является NP-полной. В [5, 6] было показано, что эта задача отличается от задачи поиска минимального порядка диапазона для радиораскраски графа. Таким образом, из доказательства NP-полноты в [12] не следует NP-полнота задачи поиска минимального порядка диапазона для радиораскраски графа, доказанная в [5, 6]. В [12] также был предложен аппроксимационный алгоритм с коэффициентом 9 для раскраски на расстоянии 2 для планарных графов. | ||
Независимо и параллельно в своей работе [1] Агнарссон и Хальдорссон представили алгоритмы | Независимо и параллельно в своей работе [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]. В той же работе авторы представили аппроксимационные алгоритмы для решения этой задачи для некоторых интересных семейств графов: [[внешнепланарный граф|внешнепланарных]] графов, [[древесная ширина графа|графов с ограниченной древесной шириной]], [[перестановочный граф|перестановочных]] и [[расщепляемый граф|расщепляемых графов]]. | ||
== Применение == | == Применение == | ||