4501
правка
Радиораскраска в планарных графах: различия между версиями
Перейти к навигации
Перейти к поиску
м
Радиораскраска в планарных графах (посмотреть исходный код)
Версия от 14:32, 1 октября 2023
, 1 октября 2023нет описания правки
Irina (обсуждение | вклад) мНет описания правки |
Irina (обсуждение | вклад) мНет описания правки |
||
| Строка 54: | Строка 54: | ||
• Вначале было показано, что количество цветов, используемое при нахождении ''минимального порядка диапазона'' для радиораскраски графа G, отличается от хроматического числа квадрата этого графа – <math>\chi (G^2) \;</math>. В частности, оно может быть больше <math>\chi (G^2) \;</math>. | • Вначале было показано, что количество цветов, используемое при нахождении ''минимального порядка диапазона'' для радиораскраски графа G, отличается от хроматического числа квадрата этого графа – <math>\chi (G^2) \;</math>. В частности, оно может быть больше <math>\chi (G^2) \;</math>. | ||
• Затем было доказано, что задача радиораскраски для графов общего вида с трудом поддается аппроксимации (за исключением случая NP = ZPP – класса задач с рандомизированными алгоритмами с нулевой ошибкой и полиномиальным временем | • Затем было доказано, что задача радиораскраски для графов общего вида с трудом поддается аппроксимации (за исключением случая NP = ZPP – класса задач с рандомизированными алгоритмами с нулевой ошибкой и полиномиальным временем выполнения) с коэффициентом <math>n^{1/2 - \epsilon} \;</math> (для любого <math>\epsilon > 0 \;</math>), где n – количество вершин графа. Однако при рассмотрении некоторых специальных разновидностей графов задача становится проще. | ||
Было показано, что задачи нахождения минимального диапазона и минимального порядка диапазона для радиораскраски являются NP-полными для планарных графов. Заметим, что некоторые комбинаторные задачи остаются сложными и для планарных графов, притом доказать их сложность также непросто, поскольку при этом необходимо использовать «планарные приспособления», сложные для нахождения и понимания. | Было показано, что задачи нахождения минимального диапазона и минимального порядка диапазона для радиораскраски являются NP-полными для планарных графов. Заметим, что некоторые комбинаторные задачи остаются сложными и для планарных графов, притом доказать их сложность также непросто, поскольку при этом необходимо использовать «планарные приспособления», сложные для нахождения и понимания. | ||
• Был представлен алгоритм с временем | • Был представлен алгоритм с временем выполнения <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] временная сложность аппроксимационного алгоритма была улучшена, также был представлен намного более простой алгоритм для проверки и внедрения, не требующий на входе планарного вложения. | ||