4501
правка
Радиораскраска в планарных графах: различия между версиями
Перейти к навигации
Перейти к поиску
м
Радиораскраска в планарных графах (посмотреть исходный код)
Версия от 13:41, 12 апреля 2016
, 12 апреля 2016→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 58: | Строка 58: | ||
Было показано, что задачи нахождения минимального диапазона и минимального порядка диапазона для радиораскраски являются NP-полными для планарных графов. Заметим, что некоторые комбинаторные задачи остаются сложными и для планарных графов, притом доказать их сложность также непросто, поскольку при этом необходимо использовать «планарные приспособления», сложные для нахождения и понимания. | Было показано, что задачи нахождения минимального диапазона и минимального порядка диапазона для радиораскраски являются NP-полными для планарных графов. Заметим, что некоторые комбинаторные задачи остаются сложными и для планарных графов, притом доказать их сложность также непросто, поскольку при этом необходимо использовать «планарные приспособления», сложные для нахождения и понимания. | ||
• Был представлен алгоритм с временем исполнения <math>O(n \Delta (G)) \;</math>, аппроксимирующий минимальный порядок радиораскраски, X_{ | • Был представлен алгоритм с временем исполнения <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] временная сложность алгоритма аппроксимации была улучшена, также был представлен намного более простой алгоритм для проверки и внедрения, не требующий на входе планарного вложения. | ||