4551
правка
Связное доминирующее множество: различия между версиями
Перейти к навигации
Перейти к поиску
Связное доминирующее множество (посмотреть исходный код)
Версия от 13:57, 22 января 2013
, 22 января 2013→История вопроса
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 13: | Строка 13: | ||
== История вопроса == | == История вопроса == | ||
Задача нахождения связного доминирующего множества исследовалась в теории графов много лет [ ]. В последнее время ее актуальность значительно выросла в связи с применением в области беспроводных сетей, а именно – для построения виртуальных магистралей [ ]. Гуха и Хуллер [10] предложили двухступенчатую схему «жадной» аппроксимации для нахождения минимального связного доминирующего множества в графах общего вида и показали, что ее коэффициент эффективности равен 3 + ln | Задача нахождения связного доминирующего множества исследовалась в теории графов много лет [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>. Важность этих работ заключается в том, что используемые в жадном алгоритме гармонические функции не являются субмодулярными. | ||
Гуха и Хуллер [ ] привели доказательство отрицательного результата, заключающегося в следующем: не существует аппроксимации с полиномиальным временем исполнения и коэффициентом эффективности pin Л для p< 1, за исключением случая NP С DTIME(nO(lnlnn)). Как показано в [ ], доминирующие множества не поддаются произвольно качественной аппроксимации, за исключением случаев, когда P почти равно NP. Эти результаты переносят фокус внимания с графов общего вида на графы единичных дисков, поскольку граф единичных дисков представляет собой базовую модель для беспроводных сенсорных сетей, и для графов единичных дисков построение МСДМ имеет аппроксимацию с полиномиальным временем исполнения и константным коэффициентом эффективности. Хотя этот константный коэффициент время от времени удается улучшить [1, 2, 19, 24], Чен и коллеги поставили точку в этом вопросе, доказав существование схемы аппроксимации с полиномиальным временем исполнения (PTAS) для графов единичных дисков. Это значит, что теоретически коэффициент эффективности для алгоритма аппроксимации с полиномиальным временем исполнения может оказаться не выше 1 + " для любого положительного ". | Гуха и Хуллер [ ] привели доказательство отрицательного результата, заключающегося в следующем: не существует аппроксимации с полиномиальным временем исполнения и коэффициентом эффективности pin Л для p< 1, за исключением случая NP С DTIME(nO(lnlnn)). Как показано в [ ], доминирующие множества не поддаются произвольно качественной аппроксимации, за исключением случаев, когда P почти равно NP. Эти результаты переносят фокус внимания с графов общего вида на графы единичных дисков, поскольку граф единичных дисков представляет собой базовую модель для беспроводных сенсорных сетей, и для графов единичных дисков построение МСДМ имеет аппроксимацию с полиномиальным временем исполнения и константным коэффициентом эффективности. Хотя этот константный коэффициент время от времени удается улучшить [1, 2, 19, 24], Чен и коллеги поставили точку в этом вопросе, доказав существование схемы аппроксимации с полиномиальным временем исполнения (PTAS) для графов единичных дисков. Это значит, что теоретически коэффициент эффективности для алгоритма аппроксимации с полиномиальным временем исполнения может оказаться не выше 1 + " для любого положительного ". | ||