Аноним

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

Материал из WEGA
 
(не показаны 3 промежуточные версии 2 участников)
Строка 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) значение решения уменьшается при сжатии ребер графа и, возможно, при удалении ребер. Многие задачи являются двумерными; можно привести такие классические примеры, как [[вершинное покрытие]], [[доминирующее множество]] и [[разрывающее множество]] вершин.


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




Следующие три класса задач касаются исключения миноров. Пусть дано ребро e = {v, w} в графе G. [[Сжатие ребра]] e в графе G заключается в определении вершин v и w в G и удалении всех циклов и дублирующихся ребер. Граф H, полученный в результате последовательности таких операций сжатия ребер в исходном графе G, называется ''сжатием'' графа G. Граф H называется [[минор графа|минором]] графа G, если H является подграфом некоторого сжатия G. Класс графов C является ''замкнутым относительно операции взятия минора'', если любой минор любого графа из C также является членом C. Класс графов C, замкнутый относительно операции взятия минора, является ''свободным от H-миноров'', если <math>H \notin C \;</math>. В более общем смысле, термин «свободный от H-миноров» относится к любому классу графов, замкнутому относительно операции взятия минора, который не включает некоторый фиксированный граф H. ''Граф с однократным пересечением'' представляет собой минор графа, который может быть изображен на плоскости так, что в нем будет пересекаться не более одной пары ребер. Класс графов, замкнутый относительно операции взятия минора, является ''свободным от миноров с однократным пересечением'', если из него исключен фиксированный граф с однократным пересечением. [[Апексный граф|Апексным графом]] называется граф, который становится планарным при удалении из него некоторой вершины. Класс графов является ''свободным от апексных миноров'', если из него исключен некоторый фиксированный апексный граф.
Следующие три класса задач касаются исключения миноров. Пусть дано ребро e = {v, w} в графе G. [[Сжатие ребра]] e в графе G заключается в определении вершин v и w в G и удалении всех циклов и дублирующихся ребер. Граф H, полученный в результате последовательности таких операций сжатия ребер в исходном графе G, называется ''сжатием'' графа G. Граф H называется [[минор графа|минором]] графа G, если H является подграфом некоторого сжатия G. Класс графов C является ''замкнутым относительно операции взятия минора'', если любой минор любого графа из C также является членом C. Класс графов C, замкнутый относительно операции взятия минора, является ''свободным от H-миноров'', если <math>H \notin C \;</math>. В более общем смысле, термин «свободный от H-миноров» относится к любому классу графов, замкнутому относительно операции взятия минора, который не включает некоторый фиксированный граф H. ''Граф с однократным пересечением'' представляет собой минор графа, который может быть изображен на плоскости так, что в нем будет пересекаться не более одной пары ребер. Класс графов, замкнутый относительно операции взятия минора, является ''свободным от миноров с однократным пересечением'', если из него исключен фиксированный граф с однократным пересечением. [[Apex graph|Апексным графом]] называется граф, который становится планарным при удалении из него некоторой вершины. Класс графов является ''свободным от апексных миноров'', если из него исключен некоторый фиксированный апексный граф.


== Двумерные параметры ==
== Двумерные параметры ==
Строка 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:


== См. также ==
== См. также ==
* ''[[Схемы аппроксимации для задач с планарными графами]]
* ''[[Аппроксимационные схемы для задач с планарными графами]]
* ''[[Путевая ширина графа]]
* ''[[Путевая ширина графа]]
* ''[[Древесная ширина графа]]
* ''[[Древесная ширина графа]]
Строка 78: Строка 78:
1. Demaine, E.D., Fomin, F.V., Hajiaghayi, M., Thilikos, D.M.: Bidimensional parameters and local treewidth. SIAM J. Discret. Math. 18(3), 501-511 (2004)
1. Demaine, E.D., Fomin, F.V., Hajiaghayi, M., Thilikos, D.M.: Bidimensional parameters and local treewidth. SIAM J. Discret. Math. 18(3), 501-511 (2004)


2. Demaine, E.D., Fomin, F.V., Hajiaghayi, M., Thilikos, D.M.: Fixed-parameter algorithms for (k,r)-center in planar graphs and map graphs. ACM Trans. Algorithms 1(1), 33^7 (2005)
2. Demaine, E.D., Fomin, F.V., Hajiaghayi, M., Thilikos, D.M.: Fixed-parameter algorithms for (k,r)-center in planar graphs and map graphs. ACM Trans. Algorithms 1(1), 33-47 (2005)


3. Demaine, E.D., Fomin, F.V., Hajiaghayi, M.,Thilikos, D.M.: Subexponential parametrized algorithms on graphs of bounded genus and H-minor-free graphs. J. ACM 52(6), 866-893 (2005)
3. Demaine, E.D., Fomin, F.V., Hajiaghayi, M.,Thilikos, D.M.: Subexponential parametrized algorithms on graphs of bounded genus and H-minor-free graphs. J. ACM 52(6), 866-893 (2005)


4. Demaine, E.D., Hajiaghayi, M.:The bidimensionality theory and its algorithmic applications. Comput. J. To appear
4. Demaine, E.D., Hajiaghayi, M.:The bidimensionality theory and its algorithmic applications. Comput. J. 51(3) (2008)


5. Demaine, E.D., Hajiaghayi, M.: Diameter and treewidth  in minor-closed graph families, revisited. Algorithmica 40(3),211-215(2004)
5. Demaine, E.D., Hajiaghayi, M.: Diameter and treewidth  in minor-closed graph families, revisited. Algorithmica 40(3),211-215(2004)
Строка 99: Строка 99:


12. Demaine, E.D., Hajiaghayi, M., Thilikos, D.M.: The bidimensional theory of bounded-genus graphs. SIAM J. Discret. Math. 20(2), 357-371 (2006)
12. Demaine, E.D., Hajiaghayi, M., Thilikos, D.M.: The bidimensional theory of bounded-genus graphs. SIAM J. Discret. Math. 20(2), 357-371 (2006)
[[Категория: Совместное определение связанных терминов]]