4551
правка
Связное доминирующее множество: различия между версиями
Перейти к навигации
Перейти к поиску
Связное доминирующее множество (посмотреть исходный код)
Версия от 14:01, 22 января 2013
, 22 января 2013→История вопроса
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 15: | Строка 15: | ||
Задача нахождения связного доминирующего множества исследовалась в теории графов много лет [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>. Важность этих работ заключается в том, что используемые в жадном алгоритме гармонические функции не являются субмодулярными. | Задача нахождения связного доминирующего множества исследовалась в теории графов много лет [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] привели доказательство отрицательного результата, заключающегося в следующем: не существует аппроксимации с полиномиальным временем исполнения и коэффициентом эффективности <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>. | ||
Дубхаши и коллеги показали, что после построения доминирующего множества можно легко вычислить связное доминирующее множество при помощи распределенного алгоритма. Самое полное изложение результатов вычисления доминирующих множеств приведено в [18]. В частности, простая константная аппроксимация доминирующих множеств графами единичных дисков приводится в [ ]. Аппроксимация с константным коэффициентом (связных) доминирующих множеств с минимальными весами для графов единичных дисков была исследована в [ ]. Схема аппроксимации с полиномиальным временем исполнения для задачи вычисления минимального доминирующего множества для графов единичных дисков была предложена в [ ]. Кун и коллеги [ ] доказали, что максимальное независимое множество (и, следовательно, доминирующее множество) можно вычислить за асимптотически оптимальное время O(log n) для графов единичных дисков и крупного класса ограниченных графов независимости. Люби [ ] предложил элегантный локальный алгоритм для вычисления максимального независимого множества для графов общего вида с временем исполнения O(log n). Джиа и коллеги [11] предложили быструю распределенную схему аппроксимации для вычисления доминирующего множества для графов общего вида с временем исполнения O(log n). Первый распределенный алгоритм для вычисления доминирующих множеств за константное время с нетривиальным коэффициентом аппроксимации для графов общего вида был приведен в [ ]. Соответствующая нижняя граница £?(log n) считается классическим результатом для распределенного вычисления [ ]. Получить схему аппроксимации с полиномиальным временем исполнения для графов единичных дисков можно при помощи распределенного алгоритма [13]. Самый быстрый детерминистский распределенный алгоритм для вычисления доминирующих множеств на графах единичных дисков был приведен в [12], а самый быстрый рандомизированный распределенный алгоритм для них же – в [9]. | Дубхаши и коллеги показали, что после построения доминирующего множества можно легко вычислить связное доминирующее множество при помощи распределенного алгоритма. Самое полное изложение результатов вычисления доминирующих множеств приведено в [18]. В частности, простая константная аппроксимация доминирующих множеств графами единичных дисков приводится в [ ]. Аппроксимация с константным коэффициентом (связных) доминирующих множеств с минимальными весами для графов единичных дисков была исследована в [ ]. Схема аппроксимации с полиномиальным временем исполнения для задачи вычисления минимального доминирующего множества для графов единичных дисков была предложена в [ ]. Кун и коллеги [ ] доказали, что максимальное независимое множество (и, следовательно, доминирующее множество) можно вычислить за асимптотически оптимальное время O(log n) для графов единичных дисков и крупного класса ограниченных графов независимости. Люби [ ] предложил элегантный локальный алгоритм для вычисления максимального независимого множества для графов общего вида с временем исполнения O(log n). Джиа и коллеги [11] предложили быструю распределенную схему аппроксимации для вычисления доминирующего множества для графов общего вида с временем исполнения O(log n). Первый распределенный алгоритм для вычисления доминирующих множеств за константное время с нетривиальным коэффициентом аппроксимации для графов общего вида был приведен в [ ]. Соответствующая нижняя граница £?(log n) считается классическим результатом для распределенного вычисления [ ]. Получить схему аппроксимации с полиномиальным временем исполнения для графов единичных дисков можно при помощи распределенного алгоритма [13]. Самый быстрый детерминистский распределенный алгоритм для вычисления доминирующих множеств на графах единичных дисков был приведен в [12], а самый быстрый рандомизированный распределенный алгоритм для них же – в [9]. | ||