Вершинное покрытие и деревья поиска: различия между версиями

Исследование параметризованных алгоритмов для решения задачи о вершинном покрытии стимулировал проект ETH Zurich «DARWIN» в области вычислительной биологии и вычислительной биохимии (см., например, [10, 11]). Многие вычислительные задачи этого проекта – такие как множественное выравнивание последовательностей [10] и разрешение биологических конфликтов [11] – могут быть сформулированы в виде задач о вершинном покрытии, в которых значение параметра в общем случае не превышает 100. Таким образом, алгоритм с временем выполнения O(kn + 1:2852k) оказывается весьма эффективным и практичным для решения подобных задач.