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

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

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

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

Алгоритм
НЕЗАЛЕЖНА МНОЖИНА(,,)
 Вибираємо довільну вершину 
 
 Знаходимо рівні пошуку в ширину для графа  з коренем  : 
 Для всіх 
 Знаходимо компоненти  графа  після видалення рівня 
 Для всіх 
 Обчислюємо , незалежну множину з максимальною вагою для графа 
 
 Нехай  є розв'язком задачі з максимальною вагою серед 
 Повертаємо 
Зауважимо, що наведений алгоритм правдоподібний, оскільки кожна множина  є об'єднанням незалежних множин, які не перетинаються.

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

Примітки


Література

* 
* 
* 
* 
* 
* 
* 
* 
* 


