Связное доминирующее множество: различия между версиями
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) мНет описания правки |
||
| (не показано 19 промежуточных версий этого же участника) | |||
| Строка 5: | Строка 5: | ||
== Постановка задачи == | == Постановка задачи == | ||
Рассмотрим граф G = (V, E). Множество C множества V называется [[доминирующее множество|доминирующим множеством]], если каждая вершина либо принадлежит к C, либо смежна с вершиной, принадлежащей к C. Если подграф, порожденный С, является связным, то C называется ''связным доминирующим множеством''. Связное доминирующее множество минимальной мощности называется ''минимальным связным доминирующим множеством'' (МСДМ). Вычисление МСДМ представляет собой NP-полную задачу, не имеющую аппроксимации с полиномиальным временем | Рассмотрим граф G = (V, E). Множество C множества V называется [[доминирующее множество|доминирующим множеством]], если каждая вершина либо принадлежит к C, либо смежна с вершиной, принадлежащей к C. Если подграф, порожденный С, является связным, то C называется ''связным доминирующим множеством''. Связное доминирующее множество минимальной мощности называется ''минимальным связным доминирующим множеством'' (МСДМ). Вычисление МСДМ представляет собой NP-полную задачу, не имеющую аппроксимации с полиномиальным временем выполнения и коэффициентом эффективности <math>\rho\ H(\Delta\ )</math> для <math>\rho\ < 1</math>, за исключением случая <math>NP \subseteq DTIME(n^{O(lnln n)})</math>, где H – гармоническая функция, а <math>\Delta\ </math> – максимальная степень исходного графа [10]. | ||
Единичным диском называется диск с радиусом, равным единице. [[Граф единичных | Единичным диском называется диск с радиусом, равным единице. [[Граф единичных кругов]] ассоциирован с множеством единичных кругов на евклидовой плоскости. Каждая вершина является центром единичного диска. Между двумя вершинами u и v существует ребро в том и только том случае, если <math>|uv| \le 1</math>, где <math>|uv| \; </math> – евклидово расстояние между u и v. Это означает, что две вершины u и v связаны ребром в том и только том случае, если диск вершины u покрывает v, а диск v покрывает u. | ||
Вычисление МСДМ для графа единичных | Вычисление МСДМ для графа единичных кругов также является NP-полной задачей; однако можно построить неплохую аппроксимацию для ее решения; Чен и коллеги [5] представили для нее аппроксимационную схему с полиномиальным временем выполнения. | ||
== История вопроса == | == История вопроса == | ||
Задача нахождения связного доминирующего множества исследовалась в теории графов много лет [22]. В последнее время ее актуальность значительно выросла в связи с применением в области беспроводных сетей, а именно – для построения виртуальных магистралей [4]. Гуха и Хуллер [10] предложили двухступенчатую схему «жадной» аппроксимации для нахождения минимального связного доминирующего множества в графах общего вида и показали, что ее коэффициент эффективности равен <math>3 + ln \Delta\ </math>, где <math>\Delta\ </math> – максимальная степень вершины в графе. Построению одноступенчатого жадного алгоритма подобной эффективности мешает трудность нахождения субмодулярной гармонической функции. Руан и коллеги [21] успешно разработали одноступенчатый алгоритм жадной аппроксимации с лучшим коэффициентом эффективности, <math>c + ln \Delta\ </math>, для любого c > 2. Дю и коллеги [6] показали, что существует аппроксимация с полиномиальным временем | Задача нахождения связного доминирующего множества исследовалась в теории графов много лет [22]. В последнее время ее актуальность значительно выросла в связи с применением в области беспроводных сетей, а именно – для построения виртуальных магистралей [4]. Гуха и Хуллер [10] предложили двухступенчатую схему «жадной» аппроксимации для нахождения минимального связного доминирующего множества в графах общего вида и показали, что ее коэффициент эффективности равен <math>3 + ln \Delta\ </math>, где <math>\Delta\ </math> – максимальная степень вершины в графе. Построению одноступенчатого жадного алгоритма подобной эффективности мешает трудность нахождения субмодулярной гармонической функции. Руан и коллеги [21] успешно разработали одноступенчатый алгоритм жадной аппроксимации с лучшим коэффициентом эффективности, <math>c + ln \Delta\ </math>, для любого c > 2. Дю и коллеги [6] показали, что существует аппроксимация с полиномиальным временем выполнения и коэффициентом эффективности <math>a(1 + ln \Delta\ )</math> для любого <math>a > 1 \; </math>. Важность этих работ заключается в том, что используемые в жадном алгоритме гармонические функции не являются субмодулярными. | ||
Гуха и Хуллер [10] привели доказательство отрицательного результата, заключающегося в следующем: не существует аппроксимации с полиномиальным временем | Гуха и Хуллер [10] привели доказательство отрицательного результата, заключающегося в следующем: не существует аппроксимации с полиномиальным временем выполнения и коэффициентом эффективности <math>\rho\ ln \Delta\ </math> для <math>\rho\ < 1</math>, за исключением случая <math>NP \subseteq DTIME(n^{O(lnln n)})</math>. Как показано в [8], доминирующие множества не поддаются произвольно качественной аппроксимации, за исключением случаев, когда P почти равно NP. Эти результаты переносят фокус внимания с графов общего вида на графы единичных кругов, поскольку граф единичных кругов представляет собой базовую модель для беспроводных сенсорных сетей, и для графов единичных кругов построение МСДМ имеет аппроксимацию с полиномиальным временем выполнения и константным коэффициентом эффективности. Хотя этот константный коэффициент время от времени удается улучшить [1, 2, 19, 24], Чен и коллеги [5] поставили точку в этом вопросе, доказав существование аппроксимационной схемы с полиномиальным временем выполнения (PTAS) для графов единичных кругов. Это значит, что теоретически коэффициент эффективности для аппроксимационного алгоритма с полиномиальным временем выполнения может оказаться не выше <math>1 + \varepsilon\ </math> для любого положительного <math>\varepsilon\ </math>. | ||
Дубхаши и коллеги [7] показали, что после построения доминирующего множества можно легко вычислить связное доминирующее множество при помощи распределенного алгоритма. Самое полное изложение результатов вычисления доминирующих множеств приведено в [18]. В частности, в этой работе простая константная аппроксимация доминирующих множеств графами единичных | Дубхаши и коллеги [7] показали, что после построения доминирующего множества можно легко вычислить связное доминирующее множество при помощи распределенного алгоритма. Самое полное изложение результатов вычисления доминирующих множеств приведено в [18]. В частности, в этой работе простая константная аппроксимация доминирующих множеств графами единичных кругов. Аппроксимация с константным коэффициентом (связных) доминирующих множеств с минимальными весами для графов единичных кругов была исследована в [3]. Аппроксимационная схема с полиномиальным временем выполнения для задачи вычисления минимального доминирующего множества для графов единичных кругов была предложена в [20]. Кун и коллеги [14] доказали, что максимальное независимое множество (и, следовательно, доминирующее множество) можно вычислить за асимптотически оптимальное время O(log n) для графов единичных кругов и крупного класса ограниченных графов независимости. Люби [17] предложил элегантный локальный алгоритм для вычисления максимального независимого множества для графов общего вида с временем выполнения O(log n). Джиа и коллеги [11] предложили быструю распределенную аппроксимационную схему для вычисления доминирующего множества для графов общего вида с временем выполнения O(log n). Первый распределенный алгоритм для вычисления доминирующих множеств за константное время с нетривиальным коэффициентом аппроксимации для графов общего вида был приведен в [15]. Соответствующая нижняя граница <math>\Omega\ (log n) \; </math> считается классическим результатом для распределенного вычисления [16]. Получить аппроксимационную схему с полиномиальным временем выполнения для графов единичных кругов можно при помощи распределенного алгоритма [13]. Самый быстрый детерминистский распределенный алгоритм для вычисления доминирующих множеств на графах единичных кругов был приведен в [12], а самый быстрый рандомизированный распределенный алгоритм для них же – в [9]. | ||
== Основные результаты == | == Основные результаты == | ||
Построение схемы | Построение аппроксимационной схемы с полиномиальным временем выполнения для минимального связного доминирующего множества (МСДМ) базируется на факте существования схемы с полиномиальным временем выполнения и константным коэффициентом эффективности. Этот факт довольно легко обнаружить. Прежде всего, заметим, что единичный диск содержит не более пяти независимых вершин [2]. Из этого следует, что любое максимальное независимое множество имеет размер не более 1 + 4opt, где opt – размер МСДМ. Кроме того, каждое максимальное независимое множество является доминирующим множеством, и можно легко построить максимальное независимое множество с остовным деревом, состоящим из всех ребер длины 2. Все вершины этого остовного дерева образуют связное доминирующее множество размером не более 1 + 8opt. Благодаря улучшению верхней границы размера максимального независимого множества [25] и возможности соединения максимальных независимых множеств [19] значение константного коэффициента было улучшено до 6,8 для распределенного реализации алгоритма. | ||
В этом построении главным образом используются техники неадаптивного разбиения и сдвига. В общем случае ход действий примерно таков: вначале квадрат, содержащий все вершины исходного графа единичных | В этом построении главным образом используются техники неадаптивного разбиения и сдвига. В общем случае ход действий примерно таков: вначале квадрат, содержащий все вершины исходного графа единичных кругов, разделяется на решетку из небольших ячеек. Каждая из этих ячеек далее разбивается на две области – центральную и граничную. Центральная область состоит из точек, находящихся на расстоянии h от границы ячейки. Граничная область состоит из точек, расстояние от которых до границы ячейки составляет не более h + 1. Таким образом, эти области перекрываются. После этого минимальное объединение связных доминирующих множеств вычисляется в каждой ячейке для связных компонент центральной области ячейки. Основная задача состоит в том, чтобы доказать, что объединение всех таких минимальных объединений не превышает минимального связного доминирующего множества для всего графа. Для вершин, не принадлежащих к центральным областям, для вычисления доминирующего множества используется часть 8-аппроксимации, лежащая в граничных областях. Вместе с упоминавшимся ранее объединением она образует связное доминирующее множество для всего исходного графа единичных кругов. Перемещая решетку для получения разбиения по разным координатам, можно получить разбиение с граничной областью, имеющей очень малую верхнюю границу. | ||
Приведем более детальное описание процесса построения. | Приведем более детальное описание процесса построения. | ||
Пусть дан исходный связный граф единичных | Пусть дан исходный связный граф единичных кругов G = (V, E), располагающийся в квадрате <math>Q = \big\{ (x, y) | 0 \le x \le q, 0 \le y \le q \big\}\ </math>, где <math>q \le |V|</math>. Для построения приближенного решения с коэффициентом эффективности <math>1 + \varepsilon\ </math> для <math>\varepsilon\ > 0</math> выберем целое число <math>m = O((1/ \varepsilon\ )ln(1/ \varepsilon\ ))</math>. Пусть <math>p = \mathcal{b} q/m \mathcal{c} + 1</math>. Рассмотрим квадрат <math>\bar{Q} = \big\{ (x, y) | - m \le x \le mp, - m \le y \le mp \big\} </math>. Разобьем <math>\bar{Q}</math> на <math>(p + 1) \times (p + 1)</math> решеток таким образом, что каждая ячейка представляет собой квадрат <math>m \times m</math>, за исключением верхней и правой границ; следовательно, никакие две ячейки не перекрываются друг с другом. Обозначим это разбиение квадрата <math>\bar{Q}</math> как P(0) (см. рис.). В общем случае разбиение P(a) получается из P(0) в результате сдвига нижнего левого угла Q из точки (—m,—m) в точку (—m + a,—m+ a). Заметим, что в результате сдвига из P(0) в P(a) для <math>0 \le a \le m</math> квадрат Q оказывается покрыт разбиением. | ||
[[Файл:CDS_1.jpg]] | [[Файл:CDS_1.jpg]] | ||
| Строка 39: | Строка 39: | ||
Центральная область | Центральная область | ||
Пусть <math>G_e(d) \; </math> обозначает часть исходного графа G, лежащую в области <math>C_e(d) \; </math>. Точнее говоря, <math>G_e(h) \; </math> представляет собой часть графа G, лежащую в центральной области e. <math>G_e(h) \; </math> может состоять из нескольких связных компонентов. Пусть <math>K_e \; </math> обозначает подмножество вершин <math>G_e(0) \; </math> с минимальной мощностью, таких, что для каждого связного компонента H области <math>G_e(h),/math подмножество <math>K_e \; </math> содержит связную компоненту, являющуюся [[доминатор|доминатором]] H. Иными словами, <math>K_e \; </math> представляет собой минимальное объединение связных доминирующих множеств в <math>G(0) \; </math> для связных компонент <math>G_e(h) \; </math>. | Пусть <math>G_e(d) \; </math> обозначает часть исходного графа G, лежащую в области <math>C_e(d) \; </math>. Точнее говоря, <math>G_e(h) \; </math> представляет собой часть графа G, лежащую в центральной области e. <math>G_e(h) \; </math> может состоять из нескольких связных компонентов. Пусть <math>K_e \; </math> обозначает подмножество вершин <math>G_e(0) \; </math> с минимальной мощностью, таких, что для каждого связного компонента H области <math>G_e(h) \, </math> подмножество <math>K_e \; </math> содержит связную компоненту, являющуюся [[доминатор|доминатором]] H. Иными словами, <math>K_e \; </math> представляет собой минимальное объединение связных доминирующих множеств в <math>G(0) \; </math> для связных компонент <math>G_e(h) \; </math>. | ||
Теперь обозначим за K(a) объединение <math>K_e \; </math> для e по всем ячейкам разбиения P(a). K(a) обладает двумя важными свойствами. | Теперь обозначим за K(a) объединение <math>K_e \; </math> для e по всем ячейкам разбиения P(a). K(a) обладает двумя важными свойствами. | ||
'''Лемма 2. <math>|K^a| \le opt</math> для <math>0 \le a \le m - 1</math>. | '''Лемма 1.''' K(a) можно вычислить за время <math>n^{O(m^2)} \; </math>. | ||
'''Лемма 2.''' <math>|K^a| \le opt</math> для <math>0 \le a \le m - 1</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> | |||
Следовательно, K(a) можно вычислить за время | Следовательно, K(a) можно вычислить за время | ||
O( | |||
<math>\sum_e n_e^{O(m^2)} \le \bigg( \sum_e n_e \bigg) ^{O(m^2)} = n^{O(m^2)}</math> | |||
Доказательство истинности леммы 2 намного сложнее; его можно найти в [5]. | Доказательство истинности леммы 2 намного сложнее; его можно найти в [5]. | ||
Граничная область | Граничная область | ||
Пусть F – связное доминирующее множество G, удовлетворяющее неравенству | Пусть F – связное доминирующее множество G, удовлетворяющее неравенству <math>|F| \le 8opt + 1</math>. Обозначим за F(a) подмножество F, лежащее в граничной области <math>B_a(h + 1) \; </math>. Поскольку построение F занимает полиномиальное время, необходимо рассмотреть только размер F(a). | ||
Доказательство. Обозначим за | '''Лемма 3.''' Положим <math>h = 7 + 3 \mathcal{b} log_2(4m^2/ \pi\ ) \mathcal{c} </math> и <math>\mathcal{b} m/(h + 1)\mathcal{c} \ge 32/ \varepsilon\ </math>. В таком случае имеется по меньшей мере половина <math>i = 0; 1, ... , \mathcal{b} m/(h + 1)\mathcal{c} - 1</math>, таких, что <math>|F(i(h + 1))| \le \varepsilon\ \cdot opt</math>. | ||
F(a) = | |||
Доказательство. Обозначим за <math>F_H(a) \; </math> подмножество вершин F(a) с расстоянием менее h + 1 от горизонтальной (и за <math>F_V(a) \; </math> - соответственно, от вертикальной) границы некоторой ячейки в P(a). Тогда <math>F(a) = F_H(a) \cup F_V(a)</math>. Более того, все <math>F_H(i(h+1)) \; </math> для <math>i = 0; 1, ... , \mathcal{b} m/(h + 1)\mathcal{c} - 1</math> являются непересекающимися. Следовательно, | |||
<math>\sum_{i=0}^{\mathcal{b} m/(h + 1)\mathcal{c} - 1} |F_H(i(h+1))| \le |F| \le 8opt</math> | |||
Подобным же образом, все <math>F_V(i(h+1)) \; </math> для <math>i = 0; 1, ... , \mathcal{b} m/(h + 1)\mathcal{c} - 1</math> являются непересекающимися и | |||
<math>\sum_{i=0}^{\mathcal{b} m/(h + 1)\mathcal{c} - 1} |F_V(i(h+1))| \le |F| \le 8opt</math> | |||
Следовательно, | |||
<math>\sum_{i=0}^{\mathcal{b} m/(h + 1)\mathcal{c} - 1} |F(i(h+1))| \le \sum_{i=0}^{\mathcal{b} m/(h + 1)\mathcal{c} - 1} (|F_H(i(h+1))| + |F_V(i(h+1))|) \le 16opt</math> | |||
Иначе говоря, | |||
<math>\frac {1} {{\mathcal{b} m/(h + 1)\mathcal{c}}} \sum_{i=0}^{\mathcal{b} m/(h + 1)\mathcal{c} - 1} |F(i(h+1))| \le ( \varepsilon\ /2)opt</math> | |||
i=0 | |||
i | |||
< | |||
Это | Это означает, что по меньшей мере половина <math>F(i(h + 1)) \; </math> для <math>i = 0; 1, ... , \mathcal{b} m/(h + 1)\mathcal{c} - 1</math> удовлетворяет соотношению<math>|F(i(h + 1))| \le \varepsilon\ \cdot opt</math>. □ | ||
Окончательный результат | Окончательный результат | ||
Теперь рассмотрим K(a) и F(a). Согласно леммам 2 и 3, существуют <math>a \in \big\{ 0, h + 1, ... , (\mathcal{b} m/(h + 1)\mathcal{c} - 1)(h + 1) \big\} </math>, такие, что | |||
<math>|K(a) \cup F(a)| \le (1 + \varepsilon\ )opt</math>. | |||
'''Лемма 4.''' Для <math>0 \le a \le m — 1</math>, <math>K(a) \cup F(a)</math> представляет собой связное доминирующее множество для исходного связного графа G. | |||
Доказательство. Очевидно, что <math>K(a) \cup F(a)</math> является доминирующим множеством для исходного графа G. Его связность можно показать следующим образом. Заметим, что центральная и граничная области перекрываются на область шириной 1. Таким образом, для любого связного компонента H подграфа <math>G_e(h) \; </math>, у F(a) имеется вершина в H. Следовательно, F(a) должен иметь связь с любым связным доминирующим множеством для H, особенно с <math>D_H \; </math> в K(a). Это означает, что <math>D_H \; </math> восстанавливает связи с F, потерянные в результате отрезания части в H. Следовательно, связность <math>K(a) \cup F(a)</math> следует из связности F. □ | |||
Суммируя вышеприведенные положения, получаем следующий результат: | |||
'''Теорема 1.''' Существует <math>(1 + \varepsilon\ )</math>-аппроксимация для построения минимального связного доминирующего множества в связных графах единичных кругов, время выполнения которой составляет <math>n^{O((1/ \varepsilon\ )log(1/ \varepsilon\ )^2)}</math>. | |||
== Применение == | == Применение == | ||
Важной областью применения связных доминирующих множеств является построение виртуальных магистралей для беспроводных сетей, особенно для беспроводных сенсорных сетей [ ]. Топология беспроводной сенсорной сети часто представляет собой граф единичных | Важной областью применения связных доминирующих множеств является построение виртуальных магистралей для беспроводных сетей, особенно для беспроводных сенсорных сетей [4]. Топология беспроводной сенсорной сети часто представляет собой граф единичных кругов. | ||
== Открытые вопросы == | == Открытые вопросы == | ||
В общем случае топология беспроводной сенсорной сети представляет собой граф | В общем случае топология беспроводной сенсорной сети представляет собой [[граф кругов]]; иначе говоря, каждая вершина ассоциируется с диском. Разные диски могут иметь различный размер. Ребро из вершины u в вершину v существует в том и только том случае, если диск u покрывает v. Виртуальная магистраль в графах кругов представляет собой подмножество вершин, порождающее [[сильно связный подграф]], такой, что каждая вершина, не принадлежащая к подмножеству, имеет входящее ребро из вершины подмножества, а также исходящее ребро, ведущее к вершине подмножества. Такая виртуальная магистраль может рассматриваться как связное доминирующее множество в графе кругов. Вопрос о том, существует ли аппроксимация с полиномиальным временем выполнения и константным коэффициентом эффективности, до сих пор остается открытым. Тай и коллеги [23] достигли в этом отношении определенных успехов. | ||
== См. также == | == См. также == | ||
| Строка 120: | Строка 118: | ||
* ''[[Точные алгоритмы построения доминирующего множества]] | * ''[[Точные алгоритмы построения доминирующего множества]] | ||
* ''[[Жадные алгоритмы покрытия множества]] | * ''[[Жадные алгоритмы покрытия множества]] | ||
* ''[[ | * ''[[Остовное дерево с максимальным количеством листьев]] | ||
== Литература == | |||
1. Alzoubi, K.M., Wan, P.-J., Frieder, O.: Message-optimal connected dominating sets in mobile ad hoc networks. In: ACM MOBIHOC, Lausanne, Switzerland, 09-11 June 2002 | |||
2. Alzoubi, K.M., P.-J.Wan, Frieder, O.: New Distributed Algorithm for Connected Dominating Set in Wireless Ad Hoc Networks. In: HICSS35, Hawaii, January 2002 | 2. Alzoubi, K.M., P.-J.Wan, Frieder, O.: New Distributed Algorithm for Connected Dominating Set in Wireless Ad Hoc Networks. In: HICSS35, Hawaii, January 2002 | ||
3. Ambuhl, C., Erlebach, T., Mihalak, M., Nunkesser, M.: Constant-Factor Approximation for Minimum-Weight (Connected) Dominating Sets in Unit Disk Graphs. In: LNCS, vol.4110, pp 3-14. Springer, Berlin (2006) | 3. Ambuhl, C., Erlebach, T., Mihalak, M., Nunkesser, M.: Constant-Factor Approximation for Minimum-Weight (Connected) Dominating Sets in Unit Disk Graphs. In: LNCS, vol.4110, pp 3-14. Springer, Berlin (2006) | ||
4. Blum, J., Ding, M., Thaeler, A., Cheng, X.: Applications of Connected Dominating Sets in Wireless Networks. In: Du, D.-Z., Pardalos, P. (eds.) Handbook of Combinatorial Optimization, pp. 329-369. Kluwer Academic (2004) | 4. Blum, J., Ding, M., Thaeler, A., Cheng, X.: Applications of Connected Dominating Sets in Wireless Networks. In: Du, D.-Z., Pardalos, P. (eds.) Handbook of Combinatorial Optimization, pp. 329-369. Kluwer Academic (2004) | ||
5. Cheng, X., Huang, X., Li, D., Wu, W., Du, D.-Z.: A polynomial-time approximation scheme for minimum connected dominating set in ad hoc wireless networks. Networks 42,202-208 (2003) | 5. Cheng, X., Huang, X., Li, D., Wu, W., Du, D.-Z.: A polynomial-time approximation scheme for minimum connected dominating set in ad hoc wireless networks. Networks 42,202-208 (2003) | ||
6. Du, D.-Z., Graham, R.L., Pardalos, P.M., Wan, P.-J., Wu, W., Zhao, W.: Analysis of greedy approximations with nonsubmodular potential functions. In: Proceedings of the 19th annual ACM-SIAM Symposium on Discrete Algorithms (SODA) pp. 167-175. January 2008 | 6. Du, D.-Z., Graham, R.L., Pardalos, P.M., Wan, P.-J., Wu, W., Zhao, W.: Analysis of greedy approximations with nonsubmodular potential functions. In: Proceedings of the 19th annual ACM-SIAM Symposium on Discrete Algorithms (SODA) pp. 167-175. January 2008 | ||
7. Dubhashi, D., Mei, A., Panconesi, A., Radhakrishnan, J., Srinivasan, A.: Fast Distributed Algorithms for (Weakly) Connected Dominating Sets and Linear-Size Skeletons. In: SODA, 2003, pp. 717-724 | 7. Dubhashi, D., Mei, A., Panconesi, A., Radhakrishnan, J., Srinivasan, A.: Fast Distributed Algorithms for (Weakly) Connected Dominating Sets and Linear-Size Skeletons. In: SODA, 2003, pp. 717-724 | ||
8. Feige, U.: A Threshold of lnn for Approximating Set Cover. J.ACM 45(4) 634-652 (1998) | 8. Feige, U.: A Threshold of lnn for Approximating Set Cover. J.ACM 45(4) 634-652 (1998) | ||
9. Gfeller, B., Vicari, E.: A Randomized Distributed Algorithm for the Maximal Independent Set Problem in Growth-Bounded Graphs. In: PODC 2007 | 9. Gfeller, B., Vicari, E.: A Randomized Distributed Algorithm for the Maximal Independent Set Problem in Growth-Bounded Graphs. In: PODC 2007 | ||
10. Guha, S., Khuller, S.: Approximation algorithms for connected dominating sets. Algorithmica 20, 374-387 (1998) | 10. Guha, S., Khuller, S.: Approximation algorithms for connected dominating sets. Algorithmica 20, 374-387 (1998) | ||
11. Jia, L., Rajaraman, R., Suel, R.:An Efficient Distributed Algorithm for Constructing Small Dominating Sets. In: PODC, Newport, Rhode Island, USA, August 2001 | 11. Jia, L., Rajaraman, R., Suel, R.:An Efficient Distributed Algorithm for Constructing Small Dominating Sets. In: PODC, Newport, Rhode Island, USA, August 2001 | ||
12. Kuhn, F., Moscibroda, T., Nieberg, T., Wattenhofer, R.: Fast De terministic Distributed Maximal Independent Set Computation on Growth-Bounded Graphs. In: DISC, Cracow, Poland, September 2005 | 12. Kuhn, F., Moscibroda, T., Nieberg, T., Wattenhofer, R.: Fast De terministic Distributed Maximal Independent Set Computation on Growth-Bounded Graphs. In: DISC, Cracow, Poland, September 2005 | ||
13. Kuhn, F., Moscibroda, T., Nieberg,T., Wattenhofer, R.: Local Approximation Schemes for Ad Hoc and Sensor Networks. In: DIALM-POMC, Cologne, Germany, September 2005 | 13. Kuhn, F., Moscibroda, T., Nieberg,T., Wattenhofer, R.: Local Approximation Schemes for Ad Hoc and Sensor Networks. In: DIALM-POMC, Cologne, Germany, September 2005 | ||
14. Kuhn, F., Moscibroda, T., Wattenhofer, R.: On the Locality of Bounded Growth. In: PODC, Las Vegas, Nevada, USA, July 2005 | 14. Kuhn, F., Moscibroda, T., Wattenhofer, R.: On the Locality of Bounded Growth. In: PODC, Las Vegas, Nevada, USA, July 2005 | ||
15. Kuhn, F., Wattenhofer, R.: Constant-Time Distributed Dominating Set Approximation. In: PODC, Boston, Massachusetts, USA, July 2003 | 15. Kuhn, F., Wattenhofer, R.: Constant-Time Distributed Dominating Set Approximation. In: PODC, Boston, Massachusetts, USA, July 2003 | ||
16. Linial, N.: Locality in distributed graph algorithms. SIAM J. Comput. 21(1), 193-201 (1992) | 16. Linial, N.: Locality in distributed graph algorithms. SIAM J. Comput. 21(1), 193-201 (1992) | ||
17. Luby, M.: A Simple Parallel Algorithm for the Maximal Independent Set Problem. SIAM J. Comput. 15,1036-1053 (1986) | 17. Luby, M.: A Simple Parallel Algorithm for the Maximal Independent Set Problem. SIAM J. Comput. 15,1036-1053 (1986) | ||
18. Marathe, M.V., Breu, H., Hunt III, H.B., Ravi, S.S., Rosenkrantz, D.J.: Simple Heuristics for Unit Disk Graphs. Networks 25, 59-68(1995) | 18. Marathe, M.V., Breu, H., Hunt III, H.B., Ravi, S.S., Rosenkrantz, D.J.: Simple Heuristics for Unit Disk Graphs. Networks 25, 59-68(1995) | ||
19. Min, M., Du, H., Jia, X., Huang, X., Huang, C.-H., Wu, W.: Improving construction for connected dominating set with Steiner tree in wireless sensor networks. J. Glob. Optim. 35, 111-119 (2006) | 19. Min, M., Du, H., Jia, X., Huang, X., Huang, C.-H., Wu, W.: Improving construction for connected dominating set with Steiner tree in wireless sensor networks. J. Glob. Optim. 35, 111-119 (2006) | ||
20. Nieberg, T., Hurink, J.L.: A PTAS for the Minimum Dominating Set Problem in Unit Disk Graphs. LNCS, vol. 3879, pp. 296-306. Springer, Berlin (2006) | 20. Nieberg, T., Hurink, J.L.: A PTAS for the Minimum Dominating Set Problem in Unit Disk Graphs. LNCS, vol. 3879, pp. 296-306. Springer, Berlin (2006) | ||
21. Ruan, L., Du, H., Jia, X., Wu, W., Li, Y., Ko, K.-I.: A greedy approximation for minimum connected dominating set. Theor. Comput. Sci. 329, 325-330 (2004) | 21. Ruan, L., Du, H., Jia, X., Wu, W., Li, Y., Ko, K.-I.: A greedy approximation for minimum connected dominating set. Theor. Comput. Sci. 329, 325-330 (2004) | ||
22. Sampathkumar, E., Walikar, H.B.: The Connected Domination Number of a Graph. J. Math. Phys. Sci. 13,607-613 (1979) | 22. Sampathkumar, E., Walikar, H.B.: The Connected Domination Number of a Graph. J. Math. Phys. Sci. 13,607-613 (1979) | ||
23. Thai, M.T., Wang F., Liu, D., Zhu, S., Du, D.-Z.: Connected Dominating Sets in Wireless Networks with Different Transmission Range. IEEE Trans. Mob. Comput. 6(7), 721-730 (2007) | 23. Thai, M.T., Wang F., Liu, D., Zhu, S., Du, D.-Z.: Connected Dominating Sets in Wireless Networks with Different Transmission Range. IEEE Trans. Mob. Comput. 6(7), 721-730 (2007) | ||
24. Wan, P.-J., Alzoubi, K.M., Frieder, O.: Distributed Construction of Connected Dominating Set in Wireless Ad Hoc Networks. In: IEEE INFOCOM 2002 | 24. Wan, P.-J., Alzoubi, K.M., Frieder, O.: Distributed Construction of Connected Dominating Set in Wireless Ad Hoc Networks. In: IEEE INFOCOM 2002 | ||
25. Wu, W., Du, H., Jia, X., Li, Y., Huang, C.-H.: Minimum Connected Dominating Sets and Maximal Independent Sets in Unit Disk Graphs. Theor. Comput. Sci. 352,1 -7 (2006) | 25. Wu, W., Du, H., Jia, X., Li, Y., Huang, C.-H.: Minimum Connected Dominating Sets and Maximal Independent Sets in Unit Disk Graphs. Theor. Comput. Sci. 352,1 -7 (2006) | ||
Текущая версия от 14:24, 1 октября 2023
Связное доминирующее множество (Connected_dominating_set)
Ключевые слова и синонимы: техники разбиения
Постановка задачи
Рассмотрим граф G = (V, E). Множество C множества V называется доминирующим множеством, если каждая вершина либо принадлежит к C, либо смежна с вершиной, принадлежащей к C. Если подграф, порожденный С, является связным, то C называется связным доминирующим множеством. Связное доминирующее множество минимальной мощности называется минимальным связным доминирующим множеством (МСДМ). Вычисление МСДМ представляет собой NP-полную задачу, не имеющую аппроксимации с полиномиальным временем выполнения и коэффициентом эффективности [math]\displaystyle{ \rho\ H(\Delta\ ) }[/math] для [math]\displaystyle{ \rho\ \lt 1 }[/math], за исключением случая [math]\displaystyle{ NP \subseteq DTIME(n^{O(lnln n)}) }[/math], где H – гармоническая функция, а [math]\displaystyle{ \Delta\ }[/math] – максимальная степень исходного графа [10].
Единичным диском называется диск с радиусом, равным единице. Граф единичных кругов ассоциирован с множеством единичных кругов на евклидовой плоскости. Каждая вершина является центром единичного диска. Между двумя вершинами u и v существует ребро в том и только том случае, если [math]\displaystyle{ |uv| \le 1 }[/math], где [math]\displaystyle{ |uv| \; }[/math] – евклидово расстояние между u и v. Это означает, что две вершины u и v связаны ребром в том и только том случае, если диск вершины u покрывает v, а диск v покрывает u.
Вычисление МСДМ для графа единичных кругов также является NP-полной задачей; однако можно построить неплохую аппроксимацию для ее решения; Чен и коллеги [5] представили для нее аппроксимационную схему с полиномиальным временем выполнения.
История вопроса
Задача нахождения связного доминирующего множества исследовалась в теории графов много лет [22]. В последнее время ее актуальность значительно выросла в связи с применением в области беспроводных сетей, а именно – для построения виртуальных магистралей [4]. Гуха и Хуллер [10] предложили двухступенчатую схему «жадной» аппроксимации для нахождения минимального связного доминирующего множества в графах общего вида и показали, что ее коэффициент эффективности равен [math]\displaystyle{ 3 + ln \Delta\ }[/math], где [math]\displaystyle{ \Delta\ }[/math] – максимальная степень вершины в графе. Построению одноступенчатого жадного алгоритма подобной эффективности мешает трудность нахождения субмодулярной гармонической функции. Руан и коллеги [21] успешно разработали одноступенчатый алгоритм жадной аппроксимации с лучшим коэффициентом эффективности, [math]\displaystyle{ c + ln \Delta\ }[/math], для любого c > 2. Дю и коллеги [6] показали, что существует аппроксимация с полиномиальным временем выполнения и коэффициентом эффективности [math]\displaystyle{ a(1 + ln \Delta\ ) }[/math] для любого [math]\displaystyle{ a \gt 1 \; }[/math]. Важность этих работ заключается в том, что используемые в жадном алгоритме гармонические функции не являются субмодулярными.
Гуха и Хуллер [10] привели доказательство отрицательного результата, заключающегося в следующем: не существует аппроксимации с полиномиальным временем выполнения и коэффициентом эффективности [math]\displaystyle{ \rho\ ln \Delta\ }[/math] для [math]\displaystyle{ \rho\ \lt 1 }[/math], за исключением случая [math]\displaystyle{ NP \subseteq DTIME(n^{O(lnln n)}) }[/math]. Как показано в [8], доминирующие множества не поддаются произвольно качественной аппроксимации, за исключением случаев, когда P почти равно NP. Эти результаты переносят фокус внимания с графов общего вида на графы единичных кругов, поскольку граф единичных кругов представляет собой базовую модель для беспроводных сенсорных сетей, и для графов единичных кругов построение МСДМ имеет аппроксимацию с полиномиальным временем выполнения и константным коэффициентом эффективности. Хотя этот константный коэффициент время от времени удается улучшить [1, 2, 19, 24], Чен и коллеги [5] поставили точку в этом вопросе, доказав существование аппроксимационной схемы с полиномиальным временем выполнения (PTAS) для графов единичных кругов. Это значит, что теоретически коэффициент эффективности для аппроксимационного алгоритма с полиномиальным временем выполнения может оказаться не выше [math]\displaystyle{ 1 + \varepsilon\ }[/math] для любого положительного [math]\displaystyle{ \varepsilon\ }[/math].
Дубхаши и коллеги [7] показали, что после построения доминирующего множества можно легко вычислить связное доминирующее множество при помощи распределенного алгоритма. Самое полное изложение результатов вычисления доминирующих множеств приведено в [18]. В частности, в этой работе простая константная аппроксимация доминирующих множеств графами единичных кругов. Аппроксимация с константным коэффициентом (связных) доминирующих множеств с минимальными весами для графов единичных кругов была исследована в [3]. Аппроксимационная схема с полиномиальным временем выполнения для задачи вычисления минимального доминирующего множества для графов единичных кругов была предложена в [20]. Кун и коллеги [14] доказали, что максимальное независимое множество (и, следовательно, доминирующее множество) можно вычислить за асимптотически оптимальное время O(log n) для графов единичных кругов и крупного класса ограниченных графов независимости. Люби [17] предложил элегантный локальный алгоритм для вычисления максимального независимого множества для графов общего вида с временем выполнения O(log n). Джиа и коллеги [11] предложили быструю распределенную аппроксимационную схему для вычисления доминирующего множества для графов общего вида с временем выполнения O(log n). Первый распределенный алгоритм для вычисления доминирующих множеств за константное время с нетривиальным коэффициентом аппроксимации для графов общего вида был приведен в [15]. Соответствующая нижняя граница [math]\displaystyle{ \Omega\ (log n) \; }[/math] считается классическим результатом для распределенного вычисления [16]. Получить аппроксимационную схему с полиномиальным временем выполнения для графов единичных кругов можно при помощи распределенного алгоритма [13]. Самый быстрый детерминистский распределенный алгоритм для вычисления доминирующих множеств на графах единичных кругов был приведен в [12], а самый быстрый рандомизированный распределенный алгоритм для них же – в [9].
Основные результаты
Построение аппроксимационной схемы с полиномиальным временем выполнения для минимального связного доминирующего множества (МСДМ) базируется на факте существования схемы с полиномиальным временем выполнения и константным коэффициентом эффективности. Этот факт довольно легко обнаружить. Прежде всего, заметим, что единичный диск содержит не более пяти независимых вершин [2]. Из этого следует, что любое максимальное независимое множество имеет размер не более 1 + 4opt, где opt – размер МСДМ. Кроме того, каждое максимальное независимое множество является доминирующим множеством, и можно легко построить максимальное независимое множество с остовным деревом, состоящим из всех ребер длины 2. Все вершины этого остовного дерева образуют связное доминирующее множество размером не более 1 + 8opt. Благодаря улучшению верхней границы размера максимального независимого множества [25] и возможности соединения максимальных независимых множеств [19] значение константного коэффициента было улучшено до 6,8 для распределенного реализации алгоритма.
В этом построении главным образом используются техники неадаптивного разбиения и сдвига. В общем случае ход действий примерно таков: вначале квадрат, содержащий все вершины исходного графа единичных кругов, разделяется на решетку из небольших ячеек. Каждая из этих ячеек далее разбивается на две области – центральную и граничную. Центральная область состоит из точек, находящихся на расстоянии h от границы ячейки. Граничная область состоит из точек, расстояние от которых до границы ячейки составляет не более h + 1. Таким образом, эти области перекрываются. После этого минимальное объединение связных доминирующих множеств вычисляется в каждой ячейке для связных компонент центральной области ячейки. Основная задача состоит в том, чтобы доказать, что объединение всех таких минимальных объединений не превышает минимального связного доминирующего множества для всего графа. Для вершин, не принадлежащих к центральным областям, для вычисления доминирующего множества используется часть 8-аппроксимации, лежащая в граничных областях. Вместе с упоминавшимся ранее объединением она образует связное доминирующее множество для всего исходного графа единичных кругов. Перемещая решетку для получения разбиения по разным координатам, можно получить разбиение с граничной областью, имеющей очень малую верхнюю границу.
Приведем более детальное описание процесса построения.
Пусть дан исходный связный граф единичных кругов G = (V, E), располагающийся в квадрате [math]\displaystyle{ Q = \big\{ (x, y) | 0 \le x \le q, 0 \le y \le q \big\}\ }[/math], где [math]\displaystyle{ q \le |V| }[/math]. Для построения приближенного решения с коэффициентом эффективности [math]\displaystyle{ 1 + \varepsilon\ }[/math] для [math]\displaystyle{ \varepsilon\ \gt 0 }[/math] выберем целое число [math]\displaystyle{ m = O((1/ \varepsilon\ )ln(1/ \varepsilon\ )) }[/math]. Пусть [math]\displaystyle{ p = \mathcal{b} q/m \mathcal{c} + 1 }[/math]. Рассмотрим квадрат [math]\displaystyle{ \bar{Q} = \big\{ (x, y) | - m \le x \le mp, - m \le y \le mp \big\} }[/math]. Разобьем [math]\displaystyle{ \bar{Q} }[/math] на [math]\displaystyle{ (p + 1) \times (p + 1) }[/math] решеток таким образом, что каждая ячейка представляет собой квадрат [math]\displaystyle{ m \times m }[/math], за исключением верхней и правой границ; следовательно, никакие две ячейки не перекрываются друг с другом. Обозначим это разбиение квадрата [math]\displaystyle{ \bar{Q} }[/math] как P(0) (см. рис.). В общем случае разбиение P(a) получается из P(0) в результате сдвига нижнего левого угла Q из точки (—m,—m) в точку (—m + a,—m+ a). Заметим, что в результате сдвига из P(0) в P(a) для [math]\displaystyle{ 0 \le a \le m }[/math] квадрат Q оказывается покрыт разбиением.
Квадраты [math]\displaystyle{ Q \; }[/math] и [math]\displaystyle{ \bar{Q} }[/math]
Для каждой ячейки e (представляющей собой квадрат [math]\displaystyle{ m \times m }[/math]) [math]\displaystyle{ C_e(d) \; }[/math] обозначает множество точек в e, удаленных от границы на расстояние не менее d; [math]\displaystyle{ C_e(0) \; }[/math] представляет саму ячейку e. Обозначим [math]\displaystyle{ B_e(d) = C_e(0) - C_e(d) \; }[/math]. Зафиксируем положительное целое число [math]\displaystyle{ h = 7 + 3 \mathcal{b} log_2(4m^2/ \pi\ ) \mathcal{c} }[/math]. Назовем [math]\displaystyle{ C_e(h) \; }[/math] центральной областью ячейки e, а [math]\displaystyle{ B_e(h + 1) \; }[/math] – граничной областью ячейки e. Таким образом, центральная и граничная области каждой ячейки перекрываются на полосу единичной ширины.
Центральная область
Пусть [math]\displaystyle{ G_e(d) \; }[/math] обозначает часть исходного графа G, лежащую в области [math]\displaystyle{ C_e(d) \; }[/math]. Точнее говоря, [math]\displaystyle{ G_e(h) \; }[/math] представляет собой часть графа G, лежащую в центральной области e. [math]\displaystyle{ G_e(h) \; }[/math] может состоять из нескольких связных компонентов. Пусть [math]\displaystyle{ K_e \; }[/math] обозначает подмножество вершин [math]\displaystyle{ G_e(0) \; }[/math] с минимальной мощностью, таких, что для каждого связного компонента H области [math]\displaystyle{ G_e(h) \, }[/math] подмножество [math]\displaystyle{ K_e \; }[/math] содержит связную компоненту, являющуюся доминатором H. Иными словами, [math]\displaystyle{ K_e \; }[/math] представляет собой минимальное объединение связных доминирующих множеств в [math]\displaystyle{ G(0) \; }[/math] для связных компонент [math]\displaystyle{ G_e(h) \; }[/math].
Теперь обозначим за K(a) объединение [math]\displaystyle{ K_e \; }[/math] для e по всем ячейкам разбиения P(a). K(a) обладает двумя важными свойствами.
Лемма 1. K(a) можно вычислить за время [math]\displaystyle{ n^{O(m^2)} \; }[/math].
Лемма 2. [math]\displaystyle{ |K^a| \le opt }[/math] для [math]\displaystyle{ 0 \le a \le m - 1 }[/math].
Справедливость леммы 1 показать несложно. Заметим, что вершины квадрата со сторонами длины [math]\displaystyle{ \sqrt{2}/2 }[/math] порождают полный подграф, в котором каждая вершина доминирует все остальные вершины. Из этого следует, что минимальное доминирующее множество для вершин [math]\displaystyle{ G_e(0) \; }[/math] имеет размер не более [math]\displaystyle{ ( \mathcal{d} \sqrt{2m} \mathcal{e} )^2 }[/math]. Следовательно, размер [math]\displaystyle{ K_e \; }[/math] составляет не более [math]\displaystyle{ 3( \mathcal{d} \sqrt{2m} \mathcal{e} )^2 }[/math], поскольку любое доминирующее множество в связном графе имеет остовное дерево с ребрами длиной не более 3. Предположим, что [math]\displaystyle{ G_e(0) \; }[/math] имеет [math]\displaystyle{ n_e \; }[/math] вершин. Тогда количество кандидатов для [math]\displaystyle{ K_e \; }[/math] составляет не более
[math]\displaystyle{ \sum_{k=0}^{3( \mathcal{d} \sqrt{2m} \mathcal{e} )^2} \binom{n_e}{k} = n_e^{O(m^2)} }[/math]
Следовательно, K(a) можно вычислить за время
[math]\displaystyle{ \sum_e n_e^{O(m^2)} \le \bigg( \sum_e n_e \bigg) ^{O(m^2)} = n^{O(m^2)} }[/math]
Доказательство истинности леммы 2 намного сложнее; его можно найти в [5].
Граничная область
Пусть F – связное доминирующее множество G, удовлетворяющее неравенству [math]\displaystyle{ |F| \le 8opt + 1 }[/math]. Обозначим за F(a) подмножество F, лежащее в граничной области [math]\displaystyle{ B_a(h + 1) \; }[/math]. Поскольку построение F занимает полиномиальное время, необходимо рассмотреть только размер F(a).
Лемма 3. Положим [math]\displaystyle{ h = 7 + 3 \mathcal{b} log_2(4m^2/ \pi\ ) \mathcal{c} }[/math] и [math]\displaystyle{ \mathcal{b} m/(h + 1)\mathcal{c} \ge 32/ \varepsilon\ }[/math]. В таком случае имеется по меньшей мере половина [math]\displaystyle{ i = 0; 1, ... , \mathcal{b} m/(h + 1)\mathcal{c} - 1 }[/math], таких, что [math]\displaystyle{ |F(i(h + 1))| \le \varepsilon\ \cdot opt }[/math].
Доказательство. Обозначим за [math]\displaystyle{ F_H(a) \; }[/math] подмножество вершин F(a) с расстоянием менее h + 1 от горизонтальной (и за [math]\displaystyle{ F_V(a) \; }[/math] - соответственно, от вертикальной) границы некоторой ячейки в P(a). Тогда [math]\displaystyle{ F(a) = F_H(a) \cup F_V(a) }[/math]. Более того, все [math]\displaystyle{ F_H(i(h+1)) \; }[/math] для [math]\displaystyle{ i = 0; 1, ... , \mathcal{b} m/(h + 1)\mathcal{c} - 1 }[/math] являются непересекающимися. Следовательно,
[math]\displaystyle{ \sum_{i=0}^{\mathcal{b} m/(h + 1)\mathcal{c} - 1} |F_H(i(h+1))| \le |F| \le 8opt }[/math]
Подобным же образом, все [math]\displaystyle{ F_V(i(h+1)) \; }[/math] для [math]\displaystyle{ i = 0; 1, ... , \mathcal{b} m/(h + 1)\mathcal{c} - 1 }[/math] являются непересекающимися и
[math]\displaystyle{ \sum_{i=0}^{\mathcal{b} m/(h + 1)\mathcal{c} - 1} |F_V(i(h+1))| \le |F| \le 8opt }[/math]
Следовательно,
[math]\displaystyle{ \sum_{i=0}^{\mathcal{b} m/(h + 1)\mathcal{c} - 1} |F(i(h+1))| \le \sum_{i=0}^{\mathcal{b} m/(h + 1)\mathcal{c} - 1} (|F_H(i(h+1))| + |F_V(i(h+1))|) \le 16opt }[/math]
Иначе говоря,
[math]\displaystyle{ \frac {1} {{\mathcal{b} m/(h + 1)\mathcal{c}}} \sum_{i=0}^{\mathcal{b} m/(h + 1)\mathcal{c} - 1} |F(i(h+1))| \le ( \varepsilon\ /2)opt }[/math]
Это означает, что по меньшей мере половина [math]\displaystyle{ F(i(h + 1)) \; }[/math] для [math]\displaystyle{ i = 0; 1, ... , \mathcal{b} m/(h + 1)\mathcal{c} - 1 }[/math] удовлетворяет соотношению[math]\displaystyle{ |F(i(h + 1))| \le \varepsilon\ \cdot opt }[/math]. □
Окончательный результат
Теперь рассмотрим K(a) и F(a). Согласно леммам 2 и 3, существуют [math]\displaystyle{ a \in \big\{ 0, h + 1, ... , (\mathcal{b} m/(h + 1)\mathcal{c} - 1)(h + 1) \big\} }[/math], такие, что
[math]\displaystyle{ |K(a) \cup F(a)| \le (1 + \varepsilon\ )opt }[/math].
Лемма 4. Для [math]\displaystyle{ 0 \le a \le m — 1 }[/math], [math]\displaystyle{ K(a) \cup F(a) }[/math] представляет собой связное доминирующее множество для исходного связного графа G.
Доказательство. Очевидно, что [math]\displaystyle{ K(a) \cup F(a) }[/math] является доминирующим множеством для исходного графа G. Его связность можно показать следующим образом. Заметим, что центральная и граничная области перекрываются на область шириной 1. Таким образом, для любого связного компонента H подграфа [math]\displaystyle{ G_e(h) \; }[/math], у F(a) имеется вершина в H. Следовательно, F(a) должен иметь связь с любым связным доминирующим множеством для H, особенно с [math]\displaystyle{ D_H \; }[/math] в K(a). Это означает, что [math]\displaystyle{ D_H \; }[/math] восстанавливает связи с F, потерянные в результате отрезания части в H. Следовательно, связность [math]\displaystyle{ K(a) \cup F(a) }[/math] следует из связности F. □
Суммируя вышеприведенные положения, получаем следующий результат:
Теорема 1. Существует [math]\displaystyle{ (1 + \varepsilon\ ) }[/math]-аппроксимация для построения минимального связного доминирующего множества в связных графах единичных кругов, время выполнения которой составляет [math]\displaystyle{ n^{O((1/ \varepsilon\ )log(1/ \varepsilon\ )^2)} }[/math].
Применение
Важной областью применения связных доминирующих множеств является построение виртуальных магистралей для беспроводных сетей, особенно для беспроводных сенсорных сетей [4]. Топология беспроводной сенсорной сети часто представляет собой граф единичных кругов.
Открытые вопросы
В общем случае топология беспроводной сенсорной сети представляет собой граф кругов; иначе говоря, каждая вершина ассоциируется с диском. Разные диски могут иметь различный размер. Ребро из вершины u в вершину v существует в том и только том случае, если диск u покрывает v. Виртуальная магистраль в графах кругов представляет собой подмножество вершин, порождающее сильно связный подграф, такой, что каждая вершина, не принадлежащая к подмножеству, имеет входящее ребро из вершины подмножества, а также исходящее ребро, ведущее к вершине подмножества. Такая виртуальная магистраль может рассматриваться как связное доминирующее множество в графе кругов. Вопрос о том, существует ли аппроксимация с полиномиальным временем выполнения и константным коэффициентом эффективности, до сих пор остается открытым. Тай и коллеги [23] достигли в этом отношении определенных успехов.
См. также
- Доминирующее множество
- Точные алгоритмы построения доминирующего множества
- Жадные алгоритмы покрытия множества
- Остовное дерево с максимальным количеством листьев
Литература
1. Alzoubi, K.M., Wan, P.-J., Frieder, O.: Message-optimal connected dominating sets in mobile ad hoc networks. In: ACM MOBIHOC, Lausanne, Switzerland, 09-11 June 2002
2. Alzoubi, K.M., P.-J.Wan, Frieder, O.: New Distributed Algorithm for Connected Dominating Set in Wireless Ad Hoc Networks. In: HICSS35, Hawaii, January 2002
3. Ambuhl, C., Erlebach, T., Mihalak, M., Nunkesser, M.: Constant-Factor Approximation for Minimum-Weight (Connected) Dominating Sets in Unit Disk Graphs. In: LNCS, vol.4110, pp 3-14. Springer, Berlin (2006)
4. Blum, J., Ding, M., Thaeler, A., Cheng, X.: Applications of Connected Dominating Sets in Wireless Networks. In: Du, D.-Z., Pardalos, P. (eds.) Handbook of Combinatorial Optimization, pp. 329-369. Kluwer Academic (2004)
5. Cheng, X., Huang, X., Li, D., Wu, W., Du, D.-Z.: A polynomial-time approximation scheme for minimum connected dominating set in ad hoc wireless networks. Networks 42,202-208 (2003)
6. Du, D.-Z., Graham, R.L., Pardalos, P.M., Wan, P.-J., Wu, W., Zhao, W.: Analysis of greedy approximations with nonsubmodular potential functions. In: Proceedings of the 19th annual ACM-SIAM Symposium on Discrete Algorithms (SODA) pp. 167-175. January 2008
7. Dubhashi, D., Mei, A., Panconesi, A., Radhakrishnan, J., Srinivasan, A.: Fast Distributed Algorithms for (Weakly) Connected Dominating Sets and Linear-Size Skeletons. In: SODA, 2003, pp. 717-724
8. Feige, U.: A Threshold of lnn for Approximating Set Cover. J.ACM 45(4) 634-652 (1998)
9. Gfeller, B., Vicari, E.: A Randomized Distributed Algorithm for the Maximal Independent Set Problem in Growth-Bounded Graphs. In: PODC 2007
10. Guha, S., Khuller, S.: Approximation algorithms for connected dominating sets. Algorithmica 20, 374-387 (1998)
11. Jia, L., Rajaraman, R., Suel, R.:An Efficient Distributed Algorithm for Constructing Small Dominating Sets. In: PODC, Newport, Rhode Island, USA, August 2001
12. Kuhn, F., Moscibroda, T., Nieberg, T., Wattenhofer, R.: Fast De terministic Distributed Maximal Independent Set Computation on Growth-Bounded Graphs. In: DISC, Cracow, Poland, September 2005
13. Kuhn, F., Moscibroda, T., Nieberg,T., Wattenhofer, R.: Local Approximation Schemes for Ad Hoc and Sensor Networks. In: DIALM-POMC, Cologne, Germany, September 2005
14. Kuhn, F., Moscibroda, T., Wattenhofer, R.: On the Locality of Bounded Growth. In: PODC, Las Vegas, Nevada, USA, July 2005
15. Kuhn, F., Wattenhofer, R.: Constant-Time Distributed Dominating Set Approximation. In: PODC, Boston, Massachusetts, USA, July 2003
16. Linial, N.: Locality in distributed graph algorithms. SIAM J. Comput. 21(1), 193-201 (1992)
17. Luby, M.: A Simple Parallel Algorithm for the Maximal Independent Set Problem. SIAM J. Comput. 15,1036-1053 (1986)
18. Marathe, M.V., Breu, H., Hunt III, H.B., Ravi, S.S., Rosenkrantz, D.J.: Simple Heuristics for Unit Disk Graphs. Networks 25, 59-68(1995)
19. Min, M., Du, H., Jia, X., Huang, X., Huang, C.-H., Wu, W.: Improving construction for connected dominating set with Steiner tree in wireless sensor networks. J. Glob. Optim. 35, 111-119 (2006)
20. Nieberg, T., Hurink, J.L.: A PTAS for the Minimum Dominating Set Problem in Unit Disk Graphs. LNCS, vol. 3879, pp. 296-306. Springer, Berlin (2006)
21. Ruan, L., Du, H., Jia, X., Wu, W., Li, Y., Ko, K.-I.: A greedy approximation for minimum connected dominating set. Theor. Comput. Sci. 329, 325-330 (2004)
22. Sampathkumar, E., Walikar, H.B.: The Connected Domination Number of a Graph. J. Math. Phys. Sci. 13,607-613 (1979)
23. Thai, M.T., Wang F., Liu, D., Zhu, S., Du, D.-Z.: Connected Dominating Sets in Wireless Networks with Different Transmission Range. IEEE Trans. Mob. Comput. 6(7), 721-730 (2007)
24. Wan, P.-J., Alzoubi, K.M., Frieder, O.: Distributed Construction of Connected Dominating Set in Wireless Ad Hoc Networks. In: IEEE INFOCOM 2002
25. Wu, W., Du, H., Jia, X., Li, Y., Huang, C.-H.: Minimum Connected Dominating Sets and Maximal Independent Sets in Unit Disk Graphs. Theor. Comput. Sci. 352,1 -7 (2006)