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

'''Теорема 3 ([1, 8]). Рассмотрим g(r)-двумерный параметр P, который может быть вычислен на графе G за время <math>h(w)n^{O(1)} \;</math> при наличии древесной декомпозиции графа G шириной не более w. Существует алгоритм, вычисляющий P на любом графе G из соответствующего P класса графов с временем выполнения <math>[h(O(g^{-1} (k))) + 2^{O(g^{-1}(k))}] n^{O(1)} \;</math>. В частности, если <math>g(r) = \Theta (r^2) \;</math> и <math>h(w) = 2^{o(w^2)} \;</math>, то это время выполнения является субэкспоненциальным относительно k.'''

'''Теорема 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> для соответствующего класса графов.'''