4501
правка
Двумерность: различия между версиями
Перейти к навигации
Перейти к поиску
→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 35: | Строка 35: | ||
Теорема 1 ([1, 8]). Если параметр P является g(r)-двумерным, то для любого графа G из семейства, ассоциированного с параметром P, tw(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 имеет в качестве минора решетку | '''Теорема 2 ([8]). Для любого фиксированного графа H любой свободный от H-миноров граф с древесной шириной w имеет в качестве минора решетку <math>\Omega(w) \times \Omega(w) \;</math>.''' | ||
Двумя главными алгоритмическими подходами к задаче двумерности являются субэкспоненциальный алгоритм общего вида с фиксированными параметрами и общая схема аппроксимации с полиномиальным временем выполнения (PTAS): | Двумя главными алгоритмическими подходами к задаче двумерности являются субэкспоненциальный алгоритм общего вида с фиксированными параметрами и общая [[схема аппроксимации с полиномиальным временем выполнения]] (PTAS): | ||
Теорема 3 ([1, 8]). Рассмотрим g(r)-двумерный параметр P, который может быть вычислен на графе G за время h(w) | Теорема 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. | ||