Любые ссылки на методы в сокращении FPT?

15

Как всем известно, знаменитая книга Гэри и Джонсона (и многие другие) дает превосходный справочник по технике редукции в классической обстановке. Существуют ли какие-либо обзоры или книги на тему техники редукции в параметризованном алгоритме, скажем, редукция fpt?

cc.complexity-theory reference-request reductions parameterized-complexity регулярность
источник
1
Смотрите Википедию и ссылки на нее.
MS Dousti

Ответы:

10

Как оригинальная книга параметризованной сложности Дауни и Феллоуз , так и новая книга Флума и Гроэ , являются хорошими ссылками для методов сокращения.

Суреш Венкат
источник
2
В частности, глава 2 последнего (озаглавленная: «Сокращения и параметризованная неразрушимость») дает хороший обзор.
MS Dousti
3
Я также цитирую книгу «Приглашение к алгоритмам с фиксированными параметрами» Р. Нидермейера, в которой во второй части рассматриваются несколько алгоритмических методов.
Матье Шапель
1
См. Страницу FPT Wiki для получения дополнительных ресурсов fpt.wikidot.com/books-and-survey-articles
yzll
5

Методы разработки алгоритмов часто помогают и в сокращениях. Поэтому, возможно, будет полезно узнать о методах, используемых для разработки алгоритмов FPT, для которых примечания Весенней школы по фиксированным параметрам и точным алгоритмам (2009) могут быть отправной точкой. В частности, вы можете посмотреть на следующие отличные обзорные доклады:

Holger
источник
3

У меня еще не было возможности открыть его, но, думаю, вас могут заинтересовать «Точные экспоненциальные алгоритмы» Фомина и Крача (с прошлого года)

Вот это его оглавление:

http://www.springerlink.com/content/978-3-642-16532-0#section=800200&page=11&locus=2

Nathann

Натанн Коэн
источник
2
Обратите внимание, что в этой книге рассматриваются только точные экспоненциальные алгоритмические методы решения и измерения сложности задач с точки зрения классической сложности вычислений: динамическое программирование, включение-исключение, измерение и завоевание, ... В этой книге нет ничего ни о каком алгоритмическом Метод сокращения, ни в классической вычислительной сложности, ни в параметризованной сложности.
Матье Шапель