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