Путевая ширина графа: различия между версиями

Подобный же подход может использоваться для параметризованных задач на планарных графах. К примеру, параметризованный алгоритм для нахождения доминирующего множества с размером, не превышающим k (или сообщения о том, что такого множества не существует) за время <math>2^{O( \sqrt{k} )} n^{O(1)}</math> может быть найден благодаря следующим наблюдениям: существует константа c, такая, что любой планарный граф, имеющий путевую ширину не менее <math>c \sqrt{k} </math>, не содержит доминирующего множества с размером не более k. Тогда для данного k алгоритм вычисляет оптимальную декомпозицию в форме ветвления для планарного графа G, и если его ширина превышает <math>c \sqrt{k} </math>, делает вывод, что у G не имеется доминирующего множества размера k. В ином случае оптимальное доминирующее множество вычисляется при помощи алгоритма динамического программирования за время <math>2^{O( \sqrt{k} )} n^{O(1)}</math>. Имеется несколько способов ограничения параметра планарного графа в терминах его путевой или древесной ширины, включая техники, сходные с подходом Бэйкер к алгоритмам аппроксимации [1], использование сепараторов либо некоторые комбинаторные методы, представленные в [16]. Другой обобщенный подход к ограничению путевой ширины планарного графа параметрами основан на исследованиях Робертсона и коллег [28], относящихся к быстрому исключению планарного графа, что приводит нас к понятию [[двумерность|двумерности]] [6]. Параметризованные алгоритмы, основанные на декомпозиции в форме ветвления, могут быть обобщены с планарных графов на графы, вложенные в поверхности, и далее на графы, исключающие фиксированный граф в качестве минора.