4551
правка
Радиораскраска в планарных графах: различия между версиями
Материал из WEGA
Радиораскраска в планарных графах (посмотреть исходный код)
Версия от 19:40, 11 апреля 2016
, 11 апреля 2016→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 50: | Строка 50: | ||
== Основные результаты == | == Основные результаты == | ||
В работах [5, 6] исследовались задачи нахождения минимального порядка диапазона, минимального диапазона и минимального порядка для радиораскраски в планарном графе G. Планарным называется граф, ребра которого могут быть уложены на плоскости без пересечений. Были получены следующие результаты: | В работах [5, 6] исследовались задачи нахождения ''минимального порядка диапазона'', ''минимального диапазона'' и ''минимального порядка' для радиораскраски в [[планарный граф|планарном графе]] G. Планарным называется граф, ребра которого могут быть уложены на плоскости без пересечений. Были получены следующие результаты: | ||
• Вначале было показано, что количество цветов, используемое при нахождении минимального порядка диапазона для радиораскраски графа G, отличается от хроматического числа квадрата этого графа – | • Вначале было показано, что количество цветов, используемое при нахождении ''минимального порядка диапазона'' для радиораскраски графа G, отличается от хроматического числа квадрата этого графа – <math>\chi (G^2) \;</math>. В частности, оно может быть больше <math>\chi (G^2) \;</math>. | ||
• Затем было доказано, что задача радиораскраски для графов общего вида с трудом поддается аппроксимации (за исключением случая | • Затем было доказано, что задача радиораскраски для графов общего вида с трудом поддается аппроксимации (за исключением случая NP = ZPP – класса задач с рандомизированными алгоритмами с нулевой ошибкой и полиномиальным временем исполнения) с коэффициентом <math>n^{1/2 - \epsilon} \;</math> (для любого <math>\epsilon > 0 \;</math>), где n – количество вершин графа. Однако при рассмотрении некоторых специальных разновидностей графов задача становится проще. | ||
Было показано, что задачи нахождения минимального диапазона и минимального порядка диапазона для радиораскраски являются NP-полными для планарных графов. Заметим, что некоторые комбинаторные задачи остаются сложными и для планарных графов, притом доказать их сложность также непросто, поскольку при этом необходимо использовать «планарные приспособления», сложные для нахождения и понимания. | Было показано, что задачи нахождения минимального диапазона и минимального порядка диапазона для радиораскраски являются NP-полными для планарных графов. Заметим, что некоторые комбинаторные задачи остаются сложными и для планарных графов, притом доказать их сложность также непросто, поскольку при этом необходимо использовать «планарные приспособления», сложные для нахождения и понимания. | ||
• Был представлен алгоритм с временем исполнения O | • Был представлен алгоритм с временем исполнения <math>O(n \Delta (G)) \;</math>, аппроксимирующий минимальный порядок радиораскраски, X_{order_, в планарном графе G ''с константным коэффициентом, который стремится к 2'' по мере возрастания максимальной степени <math>\Delta(G) \;</math> графа G. | ||
Представленный алгоритм вдохновлен теоремой Хёвела и Макгиннеса о конструктивной раскраске [9]. Построение из [ ], как показано, может привести к получению алгоритма с временем O( | Представленный алгоритм вдохновлен теоремой Хёвела и Макгиннеса о конструктивной раскраске [9]. Построение из [9], как показано, может привести к получению алгоритма с временем <math>O(n^2) \;</math>, предполагая, что планарное вложение графа G задано. В [5, 6] временная сложность алгоритма аппроксимации была улучшена, также был представлен намного более простой алгоритм для проверки и внедрения, не требующий на входе планарного вложения. | ||
• Наконец, была рассмотрена задача оценки количества различных радиораскрасок планарного графа G. Это #P-полная задача (что можно легко заметить в связи с представленным в данных работах способом редукции полноты, которая может быть выполнена консервативным образом). Авторы применяют здесь стандартную технику, сочетая цепи Маркова и новый способ формирования пар, чтобы получить доказательство быстрой сходимости (см., например, [10]) и представляют | • Наконец, была рассмотрена задача ''оценки количества различных радиораскрасок'' планарного графа G. Это #P-полная задача (что можно легко заметить в связи с представленным в данных работах способом редукции полноты, которая может быть выполнена консервативным образом). Авторы применяют здесь стандартную технику, сочетая цепи Маркова и новый способ формирования пар, чтобы получить доказательство быстрой сходимости (см., например, [10]) и представляют ''полностью полиномиальную рандомизированную схему аппроксимации'' для оценки количества радиораскрасок с <math>\lambda \;</math> цветами для планарного графа G, когда <math>\lambda \ge 4 \Delta (G) + 50 \;</math>. | ||
В [ ] и [ ] было доказано, что задача нахождения минимального диапазона для радиораскраски является NP-полной даже для графов диаметра 2. При редукции активно используются непланарные графы. В [11] было доказано, что задача раскраски квадрата графа общего вида является NP | В [8] и [7] было доказано, что задача нахождения минимального диапазона для радиораскраски является NP-полной даже для графов диаметра 2. При редукции активно используются непланарные графы. В [11] было доказано, что задача раскраски квадрата графа общего вида является NP-полной. | ||
| Строка 73: | Строка 73: | ||
Независимо и параллельно в своей работе [ ] Агнарссон и Хальдорссон представили алгоритмы аппроксимации для нахождения хроматического числа в квадратах графов и в графах более высоких степеней (Gk). В частности, они предложили алгоритм аппроксимации с коэффициентом 1:8 для раскраски квадрата планарного графа более высокой степени (A(G) > 749). Их метод использует понятие индуктивности квадрата планарного графа. | Независимо и параллельно в своей работе [ ] Агнарссон и Хальдорссон представили алгоритмы аппроксимации для нахождения хроматического числа в квадратах графов и в графах более высоких степеней (Gk). В частности, они предложили алгоритм аппроксимации с коэффициентом 1:8 для раскраски квадрата планарного графа более высокой степени (A(G) > 749). Их метод использует понятие индуктивности квадрата планарного графа. | ||
Бодлендер и коллеги [ ], также независимо и параллельно, доказали, что задача нахождения минимального диапазона для радиораскраски, которой они дали название Я-разметки, является NP-полной для планарных графов, используя подход, близкий к описанному в [5, 6]. В той же работе авторы представили алгоритмы аппроксимации для решения этой задачи для некоторых интересных семейств графов: внешнепланарных графов, графов с ограниченной древесной шириной, перестановочных и расщепляемых графов. | Бодлендер и коллеги [ ], также независимо и параллельно, доказали, что задача нахождения минимального диапазона для радиораскраски, которой они дали название Я-разметки, является NP-полной для планарных графов, используя подход, близкий к описанному в [5, 6]. В той же работе авторы представили алгоритмы аппроксимации для решения этой задачи для некоторых интересных семейств графов: внешнепланарных графов, графов с ограниченной древесной шириной, перестановочных и расщепляемых графов. | ||
== Применение == | == Применение == | ||
