Максимальная выполнимость формул в 2-КНФ: различия между версиями

Модифицировав конструкцию графа, можно решать другие задачи за время <math>O(1,732^n)</math>, такие как MAX CUT (максимальный разрез), MINIMUM BISECTION (минимальная бисекция) и SPARSEST CUT (самое неплотное сечение). В целом, любая задача оптимизации с ограничениями, в которой каждое ограничение имеет не более двух переменных, может быть решена быстрее с помощью описанного выше подхода. Более подробную информацию можно найти в работе [17] и в недавнем обзоре Вёгингера [19]. Схожая с вышеприведенным алгоритмом техника была также использована Дорном [6] с целью ускорения динамического программирования для некоторых задач на планарных графах (и вообще на графах с ограниченной путевой шириной).