4446
правок
Вершинное покрытие и деревья поиска: различия между версиями
Материал из WEGA
Вершинное покрытие и деревья поиска (посмотреть исходный код)
Версия от 19:42, 24 февраля 2018
, 24 февраля 2018→См. также
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) м (→См. также) |
||
| (не показана 1 промежуточная версия этого же участника) | |||
| Строка 11: | Строка 11: | ||
Формальное определение задачи выглядит следующим образом. Пусть 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]. | Формальное определение задачи выглядит следующим образом. Пусть 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]. | ||
== Основные результаты == | == Основные результаты == | ||
| Строка 24: | Строка 25: | ||
Таким образом, кернелизация обеспечивает эффективную предварительную обработку для последующего решения задачи о вершинном покрытии, которая позволяет работать с графами меньшего размера (т.е. с графами, размер которых зависит только от k). | Таким образом, кернелизация обеспечивает эффективную предварительную обработку для последующего решения задачи о вершинном покрытии, которая позволяет работать с графами меньшего размера (т.е. с графами, размер которых зависит только от k). | ||
== Свертка == | == Свертка == | ||
| Строка 33: | Строка 35: | ||
Операция свертки позволяет уменьшить значение параметра k без применения ветвления. Такие операции оказались весьма эффективными для разработки экспоненциальных по времени алгоритмов решения задачи о вершинном покрытии. Недавно было предложено расширение операции свертки, допускающее применение к множеству из нескольких вершин графа [6]. | Операция свертки позволяет уменьшить значение параметра k без применения ветвления. Такие операции оказались весьма эффективными для разработки экспоненциальных по времени алгоритмов решения задачи о вершинном покрытии. Недавно было предложено расширение операции свертки, допускающее применение к множеству из нескольких вершин графа [6]. | ||
== Ветвление и поиск == | == Ветвление и поиск == | ||
| Строка 68: | Строка 71: | ||
== Открытые вопросы == | == Открытые вопросы == | ||
Главный нерешенный вопрос в этом направлении исследований заключается в том, насколько далеко по нему можно зайти. Точнее говоря, насколько маленькой может быть константа c > 1, чтобы алгоритм решения задачи о вершинном покрытии имел время выполнения <math>O(c^k n^{O(1)}) \;</math>? Более тщательный анализ комбинаторных структур графов позволяет надеяться на некоторое улучшение текущей наилучшей верхней границы [4]. | Главный нерешенный вопрос в этом направлении исследований заключается в том, насколько далеко по нему можно зайти. Точнее говоря, насколько маленькой может быть константа c > 1, чтобы алгоритм решения задачи о вершинном покрытии имел время выполнения <math>O(c^k n^{O(1)}) \;</math>? Более тщательный анализ комбинаторных структур графов позволяет надеяться на некоторое улучшение текущей наилучшей верхней границы [4]. Некоторые недавно разработанные техники [6] также обещают улучшить значение верхней границы. С другой стороны, известно, что константа c не может быть произвольно близкой к 1, за исключением определенных, редко встречающихся в теории сложности случаев [8]. | ||
| Строка 78: | Строка 81: | ||
* ''[[Редукция данных для доминирования в графах]] | * ''[[Редукция данных для доминирования в графах]] | ||
* ''[[Локальные аппроксимации задач упаковки и покрытия]] | * ''[[Локальные аппроксимации задач упаковки и покрытия]] | ||
* ''[[Алгоритмы локального поиска для | * ''[[Алгоритмы локального поиска для k-КНФ]] | ||
* ''[[Кернелизация вершинного покрытия]] | * ''[[Кернелизация вершинного покрытия]] | ||
