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

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