Точные алгоритмы построения доминирующего множества: различия между версиями

Существуют другие NP-полные задачи, связанные с доминированием, которые могут быть решены при помощи алгоритма с умеренно экспоненциальным временем исполнения, основанного на вышеприведенном алгоритме нахождения минимального покрытия множества: любой экземпляр исходной задачи преобразуется в экземпляр задачи минимального покрытия множества (желательно с jUj = jSj), после чего алгоритм из теорем 3 или 4 используется для решения ее, а следовательно, и исходной задачи. Примерами таких задач являются нахождение тотального доминирующего множества, k-доминирующего множества, k-центра и минимального доминирующего множества на расщепляемых графах.

Алгоритм «Измеряй и властвуй» и прочно связанный с ним алгоритм квази-выпуклого анализа Эпстайна [ ] использовались для разработки и анализа множества алгоритмов с умеренно экспоненциальным временем исполнения для решения NP-полных задач: оптимизации, подсчета и перечисления. См., например, [2] и [6].