Техника пекарей - Bakers technique - Wikipedia

В теоретическая информатика, Техника Бейкера это метод проектирования схемы полиномиальной аппроксимации (PTAS) для проблем на планарные графы. Он назван в честь Бренда Бейкер, который объявил об этом на конференции в 1983 г. и опубликовал в Журнал ACM в 1994 г.

Идея техники Бейкера состоит в том, чтобы разбить граф на слои, чтобы проблема могла быть решена оптимально на каждом слое, а затем разумным образом объединить решения из каждого слоя, что приведет к приемлемому решению. Этот метод позволил решить следующие проблемы: изоморфизм подграфов, максимальный независимый набор, минимальное покрытие вершины, минимальный доминирующий набор, минимум набор с доминирующим краем, максимальное совпадение треугольников и многие другие.

В теория двумерности из Эрик Демейн, Федор Фомин, Hajiaghayi, и Димитриос Тиликос и его ответвление упрощение разложения (Демейн, Хаджиагайи и Каварабаяши (2005),Демейн, Хаджиагайи и Каварабаяши (2011) ) обобщает и значительно расширяет применимость техники Бейкера для огромного набора задач на планарные графы и вообще графики без фиксированного несовершеннолетнего, таких как графы ограниченного рода, а также другим классам графов, не замкнутых относительно взятия миноров, таких как 1-планарные графы.

Пример техники

Пример, который мы будем использовать для демонстрации техники Бейкера, - это максимальный вес. независимый набор проблема.

Алгоритм

НЕЗАВИСИМЫЙ-НАБОР (${ displaystyle G}$, ${ displaystyle w}$, ${ displaystyle  epsilon}$) Выберем произвольную вершину ${ displaystyle r}$    ${ displaystyle k = 1 /  epsilon}$    найти уровни поиска в ширину для ${ displaystyle G}$ укорененный в ${ displaystyle r}$ ${ displaystyle { pmod {k}}}$: ${ Displaystyle  {V_ {0}, V_ {1},  ldots, V_ {k-1} }}$    за ${ Displaystyle  ell = 0,  ldots, k-1}$        найти компоненты ${ Displaystyle G_ {1} ^ { ell}, G_ {2} ^ { ell},  ldots,}$ из ${ displaystyle G}$ после удаления ${ displaystyle V _ { ell}}$    за ${ Displaystyle я = 1,2,  ldots}$       вычислить ${ Displaystyle S_ {я} ^ { ell}}$, независимый от максимального веса набор ${ Displaystyle G_ {я} ^ { ell}}$    ${ Displaystyle S ^ { ell} =  чашка _ {i} S_ {i} ^ { ell}}$    позволять ${ Displaystyle S ^ { ell ^ {*}}}$ быть решением максимального веса среди ${ Displaystyle  {S ^ {0}, S ^ {1},  ldots, S ^ {k-1} }}$    возвращаться ${ Displaystyle S ^ { ell ^ {*}}}$

Обратите внимание, что приведенный выше алгоритм возможен, потому что каждый ${ Displaystyle S ^ { ell}}$ является объединением непересекающихся независимых множеств.

Динамическое программирование

Динамическое программирование используется, когда мы вычисляем независимый набор максимального веса для каждого ${ Displaystyle G_ {я} ^ { ell}}$. Эта динамическая программа работает, потому что каждый ${ Displaystyle G_ {я} ^ { ell}}$ это ${ displaystyle k}$-аплоскостной граф. Многие NP-полные задачи могут быть решены с помощью динамического программирования на ${ displaystyle k}$-неплоские графы. Технику Бейкера можно интерпретировать как покрытие заданных плоских графов подграфами этого типа, нахождение решения для каждого подграфа с помощью динамического программирования и склеивание решений вместе.

Рекомендации