Вершинное покрытие и деревья поиска: различия между версиями
Перейти к навигации
Перейти к поиску
Irina (обсуждение | вклад) мНет описания правки |
Irina (обсуждение | вклад) |
||
| Строка 4: | Строка 4: | ||
== Постановка задачи == | == Постановка задачи == | ||
Формальное определение задачи выглядит следующим образом. Пусть G – неориентированный граф. Подмножество C вершин графа G является [[вершинное покрытие|вершинным покрытием]] G, если хотя бы одна конечная точка каждого ребра G принадлежит к C. Пример (параметризованной) задачи о вершинном покрытии представляет собой пару (G, k), где G – граф, а <math>k \ge 0 \;</math> – целочисленный параметр; в задаче требуется определить, имеет ли граф G вершинное покрытие из k вершин. | |||
Задача о вершинном покрытии является одной из шести базовых NP-полных задач по классификации Кэри и Джонсона [7]. Это означает, что она не может быть решена за полиномиальное время, если только не верно соотношение P = NP. Однако NP-полнота задачи не устраняет необходимости в ее решении, поскольку она имеет фундаментальную значимость и широкий круг приложений. | Задача о вершинном покрытии является одной из шести базовых NP-полных задач по классификации Кэри и Джонсона [7]. Это означает, что она не может быть решена за полиномиальное время, если только не верно соотношение P = NP. Однако NP-полнота задачи не устраняет необходимости в ее решении, поскольку она имеет фундаментальную значимость и широкий круг приложений. | ||
| Строка 10: | Строка 13: | ||
Наша цель заключается в разработке параметризованных алгоритмов с временем выполнения O(f(k)p(n)) для нахождения вершинного покрытия, где p(n) – полином более низкой степени от размера входного графа n, а f(k) – неполиномиальная часть, являющаяся функцией от параметра k и независимая от n. Ожидается, что неполиномиальная функция f(k) будет насколько возможно малой. Такой алгоритм будет эффективным на практике, если параметр k будет малым. Следует отметить, что за исключением редко встречающихся в теории сложности случаев функция f(k) является по меньшей мере экспоненциальной относительно параметра k [8]. | |||
== Основные результаты == | == Основные результаты == | ||