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

Перейти к навигации Перейти к поиску
Строка 35: Строка 35:




Теорема 1 ([1, 8]). Если параметр P является g(r)-двумерным, то для любого графа G из семейства, ассоциированного с параметром P, tw(G) = Oig^iP(G))). В частности, если g(r) = 0{r2), то граница превращается в tw(G) = O(pP(G)).
'''Теорема 1 ([1, 8]). Если параметр P является g(r)-двумерным, то для любого графа G из семейства, ассоциированного с параметром P, <math>tw(G) = O(g^{-1} P(G))) \;</math>. В частности, если <math>g(r) = \Theta (r^2) \;</math>, то граница превращается в <math>tw(G) = O( \sqrt{P(G)}) \;</math>.'''




Теорема 2 ([8]). Для любого фиксированного графа H любой свободный от H-миноров граф с древесной шириной w имеет в качестве минора решетку Q{w) x Q{w).
'''Теорема 2 ([8]). Для любого фиксированного графа H любой свободный от H-миноров граф с древесной шириной w имеет в качестве минора решетку <math>\Omega(w) \times \Omega(w) \;</math>.'''




Двумя главными алгоритмическими подходами к задаче двумерности являются субэкспоненциальный алгоритм общего вида с фиксированными параметрами и общая схема аппроксимации с полиномиальным временем выполнения (PTAS):
Двумя главными алгоритмическими подходами к задаче двумерности являются субэкспоненциальный алгоритм общего вида с фиксированными параметрами и общая [[схема аппроксимации с полиномиальным временем выполнения]] (PTAS):




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




Источник — http://pco.iis.nsk.su/wega/index.php/Двумерность