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

Перейти к навигации Перейти к поиску
м
нет описания правки
мНет описания правки
Строка 1: Строка 1:
== Постановка задачи ==
== Постановка задачи ==
Теория двумерности включает обобщенные техники разработки эффективных алгоритмов с фиксированными параметрами и алгоритмов аппроксимации для широкого круга NP-полных графовых задач на широком круге графов. Эта теория применяется к графовым задачам, которые являются «двумерными» в следующем смысле: (1) значение решения для графа, представленного в виде решетки <math>k \times k \;</math>, и подобных ему графов растет вместе с k, обычно как <math>\Omega (k^2) \;</math>; (2) значение решения уменьшается при сжатии ребер графа и, возможно, при удалении ребер. Многие задачи являются двумерными; можно привести такие классические примеры, как [[вершинное покрытие]], [[доминирующее множество]] и [[разрывающее множество]] вершин.
Теория двумерности включает обобщенные техники разработки эффективных алгоритмов с фиксированными параметрами и аппроксимационных алгоритмов для широкого круга NP-полных графовых задач на широком круге графов. Эта теория применяется к графовым задачам, которые являются «двумерными» в следующем смысле: (1) значение решения для графа, представленного в виде решетки <math>k \times k \;</math>, и подобных ему графов растет вместе с k, обычно как <math>\Omega (k^2) \;</math>; (2) значение решения уменьшается при сжатии ребер графа и, возможно, при удалении ребер. Многие задачи являются двумерными; можно привести такие классические примеры, как [[вершинное покрытие]], [[доминирующее множество]] и [[разрывающее множество]] вершин.


== Классы графов ==
== Классы графов ==
Строка 42: Строка 42:




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




Строка 53: Строка 53:
Вышеприведенные теоремы широко применяются в комбинаторных и алгоритмических контекстах.
Вышеприведенные теоремы широко применяются в комбинаторных и алгоритмических контекстах.


Применяя границу параметра и древесной ширины из теоремы 1 к параметру в виде количества вершин графа, можно доказать, что каждый граф, свободный от H-миноров, с n вершинами имеет древесную ширину <math>O( \sqrt{n})</math>, что служит (повторным) доказательством теоремы о сепараторах для графов, свободных от H-миноров. Применяя границу параметра и древесной ширины из теоремы 1 к параметру в виде диаметра графа, можно доказать более сильную форму отношения Эппштейна между диаметром и древесной шириной для графов, свободных от апексных миноров. (Далее можно показать, как еще больше усилить соотношение диаметра и древесной ширины до линейного [6]). Соотношение древесной ширины и решетки из теоремы 2 может использоваться для определения границы разрыва между полуцелым и дробным алгоритмами управления несколькими товарными потоками в свободных от H-миноров графах. Оно также дает O(1)-аппроксимацию древесной ширины для графов, свободных от H-миноров. Субэкспоненциальные алгоритмы с фиксированными параметрами из теоремы 3 подтверждают либо усиливают все подобные предыдущие результаты. Эти результаты также можно обобщить для получения алгоритмов с фиксированными параметрами на произвольных графах. В частности, схемы аппроксимации с полиномиальным временем выполнения (PTAS) из теоремы 4 позволяют получить первые PTAS для связного доминирующего множества и разрывающего множества вершин даже для планарных графов. Более детальное описание всех этих результатов можно найти в [4].
Применяя границу параметра и древесной ширины из теоремы 1 к параметру в виде количества вершин графа, можно доказать, что каждый граф, свободный от H-миноров, с n вершинами имеет древесную ширину <math>O( \sqrt{n})</math>, что служит (повторным) доказательством теоремы о сепараторах для графов, свободных от H-миноров. Применяя границу параметра и древесной ширины из теоремы 1 к параметру в виде диаметра графа, можно доказать более сильную форму отношения Эппштейна между диаметром и древесной шириной для графов, свободных от апексных миноров. (Далее можно показать, как еще больше усилить соотношение диаметра и древесной ширины до линейного [6]). Соотношение древесной ширины и решетки из теоремы 2 может использоваться для определения границы разрыва между полуцелым и дробным алгоритмами управления несколькими товарными потоками в свободных от H-миноров графах. Оно также дает O(1)-аппроксимацию древесной ширины для графов, свободных от H-миноров. Субэкспоненциальные алгоритмы с фиксированными параметрами из теоремы 3 подтверждают либо усиливают все подобные предыдущие результаты. Эти результаты также можно обобщить для получения алгоритмов с фиксированными параметрами на произвольных графах. В частности, аппроксимационные схемы с полиномиальным временем выполнения (PTAS) из теоремы 4 позволяют получить первые PTAS для связного доминирующего множества и разрывающего множества вершин даже для планарных графов. Более детальное описание всех этих результатов можно найти в [4].


== Открытые вопросы ==
== Открытые вопросы ==
Строка 65: Строка 65:




Можно ли обобщить схемы аппроксимации с полиномиальным временем выполнения из теоремы 4 до алгоритмических задач более общего вида, не сопоставленных напрямую с двумерными параметрами? Один пример семейства подобных задач общего вида появляется при назначении вершинам и/или ребрам весов и необходимости вычислить, например, доминирующее множество с минимальным весом. Еще один пример такой задачи возникает при накладывании ограничений (например, на покрытие или доминирование) только на подмножества вершин и/или ребер. В качестве примеров таких задач можно привести алгоритмы построения дерева Штейнера и разрывающего множества вершин.
Можно ли обобщить аппроксимационные схемы с полиномиальным временем выполнения из теоремы 4 до алгоритмических задач более общего вида, не сопоставленных напрямую с двумерными параметрами? Один пример семейства подобных задач общего вида появляется при назначении вершинам и/или ребрам весов и необходимости вычислить, например, доминирующее множество с минимальным весом. Еще один пример такой задачи возникает при накладывании ограничений (например, на покрытие или доминирование) только на подмножества вершин и/или ребер. В качестве примеров таких задач можно привести алгоритмы построения дерева Штейнера и разрывающего множества вершин.




Строка 71: Строка 71:


== См. также ==
== См. также ==
* ''[[Схемы аппроксимации для задач с планарными графами]]
* ''[[Аппроксимационные схемы для задач с планарными графами]]
* ''[[Путевая ширина графа]]
* ''[[Путевая ширина графа]]
* ''[[Древесная ширина графа]]
* ''[[Древесная ширина графа]]
4501

правка

Навигация