Livros / notas de aula sobre complexidade parametrizada

Respostas:

23

Um bom ponto de partida é "Teoria da complexidade parametrizada", de Jörg Flum e Martin Grohe, publicada pela Springer.

Adam Bouland
fonte
17

Desculpem o auto-anúncio, mas nesta primavera estamos desenvolvendo um curso híbrido de graduação / pós-graduação em Stanford em Algoritmos e Complexidade Parametrizados. Tentamos refazer muitas das provas dos principais teoremas da literatura, de uma maneira um pouco mais acessível aos estudantes de graduação. As notas do escrevente estão (principalmente) online . No entanto, não editamos cuidadosamente todas elas, portanto ainda não as anotarei como evangelho.

Ryan Williams
fonte
6
As anotações do escriba não estão mais lá. Você vai repassá-los?
Austin Buchanan
13

Daniel Marx tem várias palestras interessantes sobre o FPT e tópicos relacionados em seu site. http://www.cs.bme.hu/~dmarx/

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

Veja também a recente coleção de ensaios / livro por ocasião do 60º aniversário de Mike Fellows. http://link.springer.com/book/10.1007/978-3-642-30891-8/page/1

Atualização (novembro de 2014): Marek Cygan et al (longa lista de autores) têm um livro intitulado "Algoritmos parametrizados" que deve ser lançado em breve (a ser publicado pela Springer). Vi rascunhos e é bastante agradável. Mais algorítmico que o livro de Flum-Grohe e também abrange vários desenvolvimentos recentes.

Chandra Chekuri
fonte
7

Consulte http://fpt.wikidot.com/books-and-survey-articles . Também prefiro Flum e Grohe, especialmente na parte da dureza, enquanto o livro de Niedermeier é mais focado no lado algorítmico. Observe que existem algumas diferenças técnicas entre os dois, por exemplo, a definição de um parâmetro como função computável de tempo polinomial no livro de Flum e Grohe, que deve ser alterada se você quiser considerar classes de espaço parametrizadas menores (consulte este artigo em Elberfeld, Stockhusen e Tantau).

frafl
fonte
4

E o livro clássico de 1999 (primeiro?) Sobre o tópico de Rod Downey e Mike Fellows?

Dois anos atrás, ouvi dizer que Rod e Mike lançariam uma segunda edição de seu livro - pode ser que esteja saindo agora. O site de Mike, http://www.mrfellows.net, deve ter mais informações. Você pode se inscrever na lista de discussão (boletim informativo), que sai a cada 2-3 meses.

Sameer Gupta
fonte
A 2ª edição foi lançada (em 2015). O nome do livro é Fundamentos da complexidade parametrizada . Sinto que este livro cobre o básico com mais detalhes do que o famoso livro de Flum e Grohe.
Cyriac Antony 27/07
2

Um livro relativamente novo é de Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk e Saket Saurabh https://www.springer.com/in/book/9783319212746

Kauray
fonte