4551
правка
Связное доминирующее множество: различия между версиями
Перейти к навигации
Перейти к поиску
м
Связное доминирующее множество (посмотреть исходный код)
Версия от 15:31, 23 января 2013
, 23 января 2013→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 44: | Строка 44: | ||
'''Лемма 1. K(a) можно вычислить за время <math>n^{O(m^2)} \; </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>. | '''Лемма 2.''' <math>|K^a| \le opt</math> для <math>0 \le a \le m - 1</math>. | ||
| Строка 64: | Строка 64: | ||
Граничная область | Граничная область | ||
Пусть F – связное доминирующее множество G, удовлетворяющее неравенству <math>|F| \le 8opt + 1</math>. Обозначим за F(a) подмножество F, лежащее в граничной области <math>B_a(h + 1) \; </math>. Поскольку построение F занимает полиномиальное время, необходимо рассмотреть только размер F(a). | |||
Лемма 3. Положим h = 7 + 3\} | '''Лемма 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>. | ||
Доказательство. Обозначим за FH(A) (FV(a)) подмножество вершин F(a) с расстоянием менее h + 1 от горизонтальной (вертикальной) границы некоторой ячейки в P(a). Тогда | Доказательство. Обозначим за FH(A) (FV(a)) подмножество вершин F(a) с расстоянием менее h + 1 от горизонтальной (вертикальной) границы некоторой ячейки в P(a). Тогда | ||