Техника пекарей - Википедия - Bakers technique

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

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

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

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

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

Алгоритм

НЕЗАВИСИМЫЙ-НАБОР (, , ) Выберем произвольную вершину         найти уровни поиска в ширину для  укорененный в  :     за         найти компоненты  из  после удаления     за        вычислить , независимый от максимального веса набор         позволять  быть решением максимального веса среди     возвращаться 

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

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

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

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

  • Бейкер, Б. (1994), "Алгоритмы приближения для NP-полных задач на плоских графах", Журнал ACM, 41 (1): 153–180, Дои:10.1145/174644.174650, S2CID  9706753.
  • Бейкер, Б. (1983), «Алгоритмы аппроксимации для NP-полных задач на плоских графах», FOCS, 24.
  • Бодландер, Х. (1988), «Динамическое программирование на графах с ограниченной шириной дерева», ИКАЛП, Конспект лекций по информатике, 317: 105–118, Дои:10.1007/3-540-19488-6_110, ISBN  978-3-540-19488-0.
  • Демейн, Э.; Hajiaghayi, M .; Каварабаяси, К. (2005), «Минорная теория алгоритмических графов: декомпозиция, аппроксимация и раскраска» (PDF), FOCS, 46: 637–646, Дои:10.1109 / SFCS.2005.14, ISBN  0-7695-2468-0, S2CID  13238254.
  • Демейн, Э.; Hajiaghayi, M .; Каварабаяси, К. (2011), "Сжатие разложения в H-минорных графах и алгоритмических приложениях", STOC, 43: 441, Дои:10.1145/1993636.1993696, HDL:1721.1/73855, ISBN  9781450306911, S2CID  16516718.
  • Демейн, Э.; Hajiaghayi, M .; Nishimura, N .; Ragde, P .; Тиликос, Д. (2004), "Алгоритмы приближения для классов графов, исключая графы с одним пересечением в качестве миноров.", J. Comput. Syst. Sci., 69 (2): 166–195, Дои:10.1016 / j.jcss.2003.12.001.
  • Эппштейн, Д. (2000), "Диаметр и ширина дерева в семействах минорно-замкнутых графов", Алгоритмика, 27 (3): 275–291, arXiv:математика / 9907126v1, Дои:10.1007 / s004530010020, S2CID  3172160.
  • Эппштейн, Д. (1995), "Изоморфизм подграфов в плоских графах и связанные с этим проблемы", СОДА, 6.
  • Григорьев Александр; Бодландер, Ханс Л. (2007), «Алгоритмы для графов, встраиваемых с несколькими пересечениями на ребро», Алгоритмика, 49 (1): 1–11, Дои:10.1007 / s00453-007-0010-х, HDL:1874/17980, МИСТЕР  2344391, S2CID  8174422.