Техника Бренды Бейкер — это метод построения приближенных схем полиномиального времени (ПСПВ, PTAS) для задач на планарных графах. Метод назван именем американской учёной в области информатики , сообщившей о методе на конференции 1983 года и опубликовавшей статью в журнале Journal of the ACM в 1994.
Идея техники Бренды Бейкер заключается в разбиении графа на уровни, так что задача может быть решена оптимально на каждом уровне, затем решения на каждом уровне комбинируются удовлетворительным способом, что приводит к реалистичному решению. Эта техника дала ПСПВ для следующих задач: задача поиска изоморфного подграфа, задача о максимальном независимом множестве, задача о вершинном покрытии, минимальное доминирующее множество, минимальное доминирующее множество рёбер многие другие.
Эрика Демайна, Фёдора Фомина, Мухаммеда Хаджигайи и Димитроса Тиликоса и её ответвление упрощённые декомпозиции обобщает и существенно расширяет область применения техники Бренды Бейкер на обширное множество задач на планарных графах и, более обще, на графах, не содержащих определённого минора, таких как графы с ограниченным родом, а также другие классы графов, не замкнутые по взятию минора, такие как 1-планарные графы.
Пример техники Пример, на котором продемонстрируем технику Бренды Бейкер — это задача нахождения максимума взвешенного независимого множества.
Алгоритм НЕЗАВИСИМОЕ МНОЖЕСТВО(,,) Выбираем произвольную вершину
Находим уровни поиска в ширину для графа с корнем : Для всех Находим компоненты графа после удаления уровня Для всех Вычисляем , независимое множество с максимальным весом для графа
Пусть является решением задачи с максимальным весом среди Возвращаем
Заметим, что приведённый алгоритм правдоподобен, поскольку каждое множество является объединением непересекающихся независимых множеств.
Динамическое программирование Динамическое программирование используется для вычисления независимого множества максимального веса для каждого . Эта задача динамического программирования работает, поскольку каждый граф является -внешнепланарным. Многие NP-полные задачи можно решить с помощью динамического программирования на -внешнепланарных графах.
Примечания
Литература
Категория:Планарные графы Категория:Аппроксимационные алгоритмы