Техніка Бренди Бейкер

Те́хніка Бре́нди Бе́йкер — метод побудови схем наближення до поліноміального часу (СНПЧ, PTAS) для задач на планарних графах. Метод названо ім'ям американської вченої в галузі інформатики Шаблон:Не перекладено, яка повідомила про метод на конференції 1983 року і опублікувала статтю в журналі Journal of the ACM у 1994.

Ідея техніки Бренди Бейкер полягає в розбитті графа на рівні, так що задачу можна розв'язати оптимально на кожному рівні, потім розв'язки на кожному рівні комбінуються задовільним способом, що дає реалістичний розв'язок. Ця техніка дала СНПЧ для таких задач: задача пошуку ізоморфного підграфа, задача про максимальну незалежну множину, задача про вершинне покриття, мінімальна домінівна множина, мінімальна домінівна множина ребер та багато інших.

Шаблон:Не перекладено Еріка Демайна, Федора Фомина, Мухаммеда Хаджигайї та Димитроса Тілікоса і її відгалуження спрощені декомпозиціїШаблон:SfnШаблон:Sfn узагальнює й істотно розширює сферу застосування техніки Бренди Бейкер на багато задач на планарных графах і, загальніше, на графах, які не містять певного мінора, таких як графи з обмеженим родом, а також інші класи графів, не замкнуті після взяття мінора, такі як 1-планарні графи.

Приклад техніки

Приклад, на якому продемонструємо техніку Бренди Бейкер — це задача знаходження максимуму зваженої незалежної множини.

Алгоритм

НЕЗАЛЕЖНА МНОЖИНА($G$,$w$,$ϵ$)

Вибираємо довільну вершину $r$
$k=1/ϵ$
Знаходимо рівні пошуку в ширину для графа $G$ з коренем $r$$(\mathrm{mod}k)$ : $\{V_0,V_1,\dots ,V_{k-1}\}$
Для всіх $\ell =0,\dots ,k-1$
Знаходимо компоненти $G_1^{\ell },G_2^{\ell },\dots ,$ графа $G$ після видалення рівня $V_{\ell }$
Для всіх $i=1,2,\dots$
Обчислюємо $S_i^{\ell }$, незалежну множину з максимальною вагою для графа $G_i^{\ell }$
$S^{\ell }={\cup }_i{S}_i^{\ell }$
Нехай $S^{{\ell }^{*}}$ є розв'язком задачі з максимальною вагою серед $\{S^0,S^1,\dots ,S^{k-1}\}$
Повертаємо $S^{{\ell }^{*}}$

Зауважимо, що наведений алгоритм правдоподібний, оскільки кожна множина $S^{\ell }$ є об'єднанням незалежних множин, які не перетинаються.

Динамічне програмування

Динамічне програмування використовується для обчислення незалежної множини максимальної ваги для кожного $G_i^{\ell }$. Ця задача динамічного програмування працює, оскільки кожен граф $G_i^{\ell }$ є $k$-зовніпланарним. Багато NP-повних задач можна розв'язати за допомогою динамічного програмування на $k$-зовніпланарних графах.

Література

• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття