Двумерность: различия между версиями

'''Теорема 4 ([7]). Рассмотрим задачу двумерности, удовлетворяющую «свойству отделимости», определенному в [4, 7]. Предположим, что эта задача может быть решена на графе G с n вершинами за время f(n, tw(G)). Предположим также, что задача может быть аппроксимирована с коэффициентом a за время g(n). Далее, для задачи двумерности со сжатием предположим далее, что оба этих алгоритма также применяются к «обобщенной форме» задачи, определенной в [4, 7]. Тогда существует алгоритм <math>(1 + \epsilon) \;</math>-аппроксимации задачи двумерности, время выполнения которого составляет <math>O(n f (n, O( \alpha^2 / \epsilon)) + n^3 g(n)) \;</math> для соответствующего класса графов.'''