Alguma referência para técnicas nas reduções do FPT?

15

Como todos sabem, o famoso livro de Garey e Johnson (e muitos outros) fornece uma excelente referência para a técnica de redução no cenário clássico. Existem pesquisas ou livros sobre o tópico da técnica de redução no algoritmo parametrizado, digamos a redução de fpt?

cc.complexity-theory reference-request reductions parameterized-complexity Regularidade
fonte
11
Veja Wikipedia e suas referências.
MS Dousti

Respostas:

10

Tanto o livro original de complexidade parametrizada de Downey and Fellows , quanto o livro mais recente de Flum e Grohe , são boas referências para técnicas de redução.

Suresh Venkat
fonte
2
Especificamente, o capítulo 2 deste último (intitulado: "Reduções e intratabilidade parametrizada") fornece uma boa pesquisa.
MS Dousti
3
Eu também citaria o livro "Convite para algoritmos de parâmetros fixos", de R. Niedermeier, no qual a segunda parte examina vários métodos algorítmicos.
Mathieu Chapelle
11
Veja a página Wiki do FPT para obter mais recursos fpt.wikidot.com/books-and-survey-articles
yzll 13/02/11
5

As técnicas para o design de algoritmos geralmente também ajudam nas reduções. Portanto, pode ser bom aprender sobre as técnicas usadas para projetar algoritmos FPT, para as quais as notas da Escola de Primavera sobre Algoritmos Exatos e Parâmetros Fixos (2009) podem ser um ponto de partida. Em particular, convém consultar as seguintes excelentes palestras gerais:

  • Dániel Marx sobre técnicas algorítmicas do FPT ( slides ).
  • Thore Husfeldt sobre Uma introdução taxonômica aos algoritmos exatos ( slides | notas da aula ).
Holger
fonte
3

Ainda não tive a oportunidade de abri-lo, mas acho que você pode estar interessado em "Algoritmos exponenciais exatos" de Fomin e Kratsch (do ano passado)

Aqui está seu índice:

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

Nathann

Nathann Cohen
fonte
2
Observe que este livro apenas pesquisa métodos algorítmicos exponenciais exatos para resolver e medir a complexidade de problemas do ponto de vista da complexidade computacional clássica: programação dinâmica, exclusão-inclusão, medida e conquista, ... Não há nada neste livro sobre algoritmos método de redução, nem na complexidade computacional clássica nem na complexidade parametrizada.
Mathieu Chapelle