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

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