4551
правка
Связное доминирующее множество: различия между версиями
Материал из WEGA
Связное доминирующее множество (посмотреть исходный код)
Версия от 14:46, 17 июля 2014
, 17 июля 2014→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 21: | Строка 21: | ||
== Основные результаты == | == Основные результаты == | ||
Построение схемы аппроксимации с полиномиальным временем исполнения для минимального связного доминирующего множества (МСДМ) базируется на факте существования схемы с полиномиальным временем исполнения и константным коэффициентом эффективности. Этот факт довольно легко обнаружить. Прежде всего, заметим, что единичный диск содержит не более пяти независимых вершин [2]. Из этого следует, что любое максимальное независимое множество имеет размер не более 1 + 4opt, где opt – размер МСДМ. Кроме того, каждое максимальное независимое множество является доминирующим множеством, и можно легко построить максимальное независимое множество с остовным деревом, состоящим из всех | Построение схемы аппроксимации с полиномиальным временем исполнения для минимального связного доминирующего множества (МСДМ) базируется на факте существования схемы с полиномиальным временем исполнения и константным коэффициентом эффективности. Этот факт довольно легко обнаружить. Прежде всего, заметим, что единичный диск содержит не более пяти независимых вершин [2]. Из этого следует, что любое максимальное независимое множество имеет размер не более 1 + 4opt, где opt – размер МСДМ. Кроме того, каждое максимальное независимое множество является доминирующим множеством, и можно легко построить максимальное независимое множество с остовным деревом, состоящим из всех ребер длины 2. Все вершины этого остовного дерева образуют связное доминирующее множество размером не более 1 + 8opt. Благодаря улучшению верхней границы размера максимального независимого множества [25] и возможности соединения максимальных независимых множеств [19] значение константного коэффициента было улучшено до 6,8 для распределенного реализации алгоритма. | ||
В этом построении главным образом используются техники неадаптивного разбиения и сдвига. В общем случае ход действий примерно таков: вначале квадрат, содержащий все вершины исходного графа единичных дисков, разделяется на решетку из небольших ячеек. Каждая из этих ячеек далее разбивается на две области – центральную и граничную. Центральная область состоит из точек, находящихся на расстоянии h от границы ячейки. Граничная область состоит из точек, расстояние от которых до границы ячейки составляет не более h + 1. Таким образом, эти области перекрываются. После этого минимальное объединение связных доминирующих множеств вычисляется в каждой ячейке для связных компонент центральной области ячейки. Основная задача состоит в том, чтобы доказать, что объединение всех таких минимальных объединений не превышает минимального связного доминирующего множества для всего графа. Для вершин, не принадлежащих к центральным областям, для вычисления доминирующего множества используется часть 8-аппроксимации, лежащая в граничных областях. Вместе с упоминавшимся ранее объединением она образует связное доминирующее множество для всего исходного графа единичных дисков. Перемещая решетку для получения разбиения по разным координатам, можно получить разбиение с граничной областью, имеющей очень малую верхнюю границу. | В этом построении главным образом используются техники неадаптивного разбиения и сдвига. В общем случае ход действий примерно таков: вначале квадрат, содержащий все вершины исходного графа единичных дисков, разделяется на решетку из небольших ячеек. Каждая из этих ячеек далее разбивается на две области – центральную и граничную. Центральная область состоит из точек, находящихся на расстоянии h от границы ячейки. Граничная область состоит из точек, расстояние от которых до границы ячейки составляет не более h + 1. Таким образом, эти области перекрываются. После этого минимальное объединение связных доминирующих множеств вычисляется в каждой ячейке для связных компонент центральной области ячейки. Основная задача состоит в том, чтобы доказать, что объединение всех таких минимальных объединений не превышает минимального связного доминирующего множества для всего графа. Для вершин, не принадлежащих к центральным областям, для вычисления доминирующего множества используется часть 8-аппроксимации, лежащая в граничных областях. Вместе с упоминавшимся ранее объединением она образует связное доминирующее множество для всего исходного графа единичных дисков. Перемещая решетку для получения разбиения по разным координатам, можно получить разбиение с граничной областью, имеющей очень малую верхнюю границу. | ||
| Строка 49: | Строка 49: | ||
Справедливость леммы 1 показать несложно. Заметим, что вершины квадрата со сторонами длины <math>\sqrt{2}/2</math> порождают полный подграф, в котором каждая вершина доминирует все остальные вершины. Из этого следует, что минимальное доминирующее множество для вершин <math>G_e(0) \; </math> имеет размер не более <math>( \mathcal{d} \sqrt{2m} \mathcal{e} )^2</math>. Следовательно, размер <math>K_e \; </math> составляет не более <math>3( \mathcal{d} \sqrt{2m} \mathcal{e} )^2</math>, поскольку любое доминирующее множество в связном графе имеет остовное дерево с | Справедливость леммы 1 показать несложно. Заметим, что вершины квадрата со сторонами длины <math>\sqrt{2}/2</math> порождают полный подграф, в котором каждая вершина доминирует все остальные вершины. Из этого следует, что минимальное доминирующее множество для вершин <math>G_e(0) \; </math> имеет размер не более <math>( \mathcal{d} \sqrt{2m} \mathcal{e} )^2</math>. Следовательно, размер <math>K_e \; </math> составляет не более <math>3( \mathcal{d} \sqrt{2m} \mathcal{e} )^2</math>, поскольку любое доминирующее множество в связном графе имеет остовное дерево с ребрами длиной не более 3. Предположим, что <math>G_e(0) \; </math> имеет <math>n_e \; </math> вершин. Тогда количество кандидатов для <math>K_e \; </math> составляет не более | ||
<math>\sum_{k=0}^{3( \mathcal{d} \sqrt{2m} \mathcal{e} )^2} \binom{n_e}{k} = n_e^{O(m^2)}</math> | <math>\sum_{k=0}^{3( \mathcal{d} \sqrt{2m} \mathcal{e} )^2} \binom{n_e}{k} = n_e^{O(m^2)}</math> | ||
