Двумерность: различия между версиями
Перейти к навигации
Перейти к поиску
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 33: | Строка 33: | ||
== Основные результаты == | == Основные результаты == | ||
Двумерность строится на базе основополагающей теории о минорах графа Робертсона и Сеймура при помощи расширения некоторых математических результатов и построения новых алгоритмических инструментов. Несколько важных результатов в задачах о двумерности были получены на основе следующих комбинаторных утверждений. Первое из них связывает любой параметр двумерности с древесной шириной, второе – древесную ширину с минорами решетки. | |||
Теорема 1 ([1, 8]). Если параметр P является g(r)-двумерным, то для любого графа G из семейства, ассоциированного с параметром P, tw(G) = Oig^iP(G))). В частности, если g(r) = 0{r2), то граница превращается в tw(G) = O(pP(G)). | |||
Теорема 2 ([8]). Для любого фиксированного графа H любой свободный от H-миноров граф с древесной шириной w имеет в качестве минора решетку Q{w) x Q{w). | |||
Двумя главными алгоритмическими подходами к задаче двумерности являются субэкспоненциальный алгоритм общего вида с фиксированными параметрами и общая схема аппроксимации с полиномиальным временем выполнения (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. | |||
Теорема 4 ([7]). Рассмотрим задачу двумерности, удовлетворяющую «свойству отделимости», определенному в [4, 7]. Предположим, что эта задача может быть решена на графе G с n вершинами за время f(n; tw(G)). Предположим также, что задача может быть аппроксимирована с коэффициентом a за время g(n). Далее, для задачи двумерности со сжатием предположим далее, что оба этих алгоритм также применяются к «обобщенное форме» задачи, определенной в [4, 7]. Тогда существует алгоритм (1 + e)-аппроксимации задачи двумерности, время выполнения которого составляет O(nf(n; O(a2/e)) + n3g(n)) для соответствующего класса графов. | |||
== Применение == | |||