Связное доминирующее множество: различия между версиями

Пусть дан исходный связный граф единичных дисков 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>. Пусть p = bq/mc + 1. Рассмотрим квадрат Q = f(x, y) \ — m < x < mp; —m < y < mpg. Разобьем Q на (p + 1) x (p + 1) решеток таким образом, что каждая ячейка представляет собой квадрат m x m, за исключением верхней и правой границ; следовательно, никакие две ячейки не перекрываются друг с другом. Обозначим это разбиение квадрата Q как P(0) (рис. 1). В общем случае разбиение P(a) получается из P(0) в результате сдвига нижнего левого угла Q из точки (—m,—m) в точку (—m + a,—m+ a). Заметим, что в результате сдвига из P(0) в P(a) для 0 < a < m квадрат Q оказывается покрыт разбиением.