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

Пусть дан исходный связный граф единичных дисков G = (V, E), располагающийся в квадрате Q = f(x, y) j 0 < x < q; 0 < y < qg, где q < jVj. Для построения приближенного решения с коэффициентом эффективности 1 + " для " > 0 выберем целое число m = O((1/")ln(1/")). Пусть 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 оказывается покрыт разбиением.