Книги / Лекционные заметки о параметризованной сложности

18

Я хотел бы узнать о параметризованной сложности (как на алгоритмической стороне, так и на жесткости). Какие книги / конспекты лекций я могу прочитать на эту тему?

Игорь Шинкарь
источник

Ответы:

23

Хорошее место для начала - «Теория параметризованной сложности» Йорга Флума и Мартина Гроэ, опубликованная Springer.

Адам Буланд
источник
17

Извините за саморекламу, но этой весной мы разрабатываем гибридный курс старшекурсников / выпускников в Стэнфорде по параметризованным алгоритмам и сложности. Мы попытались «переделать» многие доказательства основных теорем в литературе таким образом, чтобы это было несколько более доступно для студентов. Примечания писца (в основном) онлайн . Однако мы не тщательно отредактировали их все, поэтому я бы пока не воспринял эти записи как Евангелие.

Райан Уильямс
источник
6
Записки писца там больше нет. Будете ли вы их репостить?
Остин Бьюкенен
13

Даниэль Маркс имеет несколько интересных выступлений по FPT и смежным темам на своем сайте. http://www.cs.bme.hu/~dmarx/

http://www.cs.bme.hu/~dmarx/talk.php

Смотрите также недавнюю коллекцию сочинений / книг по случаю 60-летия Майка Феллоуз. http://link.springer.com/book/10.1007/978-3-642-30891-8/page/1

Обновление (ноябрь 2014 г.): у Марека Сигана и др. (Длинный список авторов) есть книга под названием «Параметризованные алгоритмы», которая должна выйти в ближайшее время (будет опубликована Springer). Я видел шашки, и это довольно приятно. Более алгоритмический, чем книга Флума-Гроэ, а также охватывает несколько последних событий.

Чандра Чекури
источник
7

См. Http://fpt.wikidot.com/books-and-survey-articles . Я также предпочитаю Флума и Гроэ, особенно в части твердости, тогда как книга Нидермейера больше сосредоточена на алгоритмической стороне. Обратите внимание , что существуют некоторые технические различия между этими двумя, например , определение параметра как полиномиальное время вычислимой функции в книге Flum и Grohe, который должен быть изменен , если один любит рассматривать меньшие параметризованные классы пространства (см эту статью по Эльберфельд, Штокхузен и Тантау).

frafl
источник
4

Как насчет классической (первой?) Книги 1999 года на тему Рода Дауни и Майка Феллоуз?

Два года назад я слышал, что Род и Майк собирались выпустить второе издание своей книги - возможно, оно вышло сейчас. Сайт Майка http://www.mrfellows.net должен иметь больше информации. Вы можете подписаться на его рассылку (рассылку), которая выходит каждые 2-3 месяца.

Самир Гупта
источник
2-е издание вышло (в 2015 году). Название книги - Основы параметризованной сложности . Я чувствую, что эта книга охватывает основы более подробно, чем знаменитая книга Флума и Гроэ.
Кириак Антоний
2

Относительно новый учебник - Марек Сиган, Федор В. Фомин, Лукаш Ковалик, Даниэль Локштанов, Даниэль Маркс, Марцин Пилипчук, Михал Пилипчук и Сакет Саураб https://www.springer.com/in/book/9783319212746

kauray
источник