4501
правка
Радиораскраска в планарных графах: различия между версиями
Перейти к навигации
Перейти к поиску
м
Радиораскраска в планарных графах (посмотреть исходный код)
Версия от 13:43, 12 апреля 2016
, 12 апреля 2016→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 62: | Строка 62: | ||
Представленный алгоритм вдохновлен теоремой Хёвела и Макгиннеса о конструктивной раскраске [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>. | ||