¿Alguna referencia para técnicas en reducciones de FPT?

15

Como todos saben, el famoso libro de Garey y Johnson (y muchos otros) proporciona una excelente referencia para la técnica de reducción en el entorno clásico. ¿Hay encuestas o libros sobre el tema de la técnica de reducción en algoritmos parametrizados, digamos la reducción de fpt?

cc.complexity-theory reference-request reductions parameterized-complexity Regularidad
fuente
1
Ver Wikipedia y sus referencias.
MS Dousti

Respuestas:

10

Tanto el libro de complejidad parametrizada original de Downey and Fellows como el libro más reciente de Flum y Grohe son buenas referencias para las técnicas de reducción.

Suresh Venkat
fuente
2
Específicamente, el capítulo 2 de este último (titulado: "Reducciones e Intractabilidad parametrizada") proporciona una buena encuesta.
MS Dousti
3
También citaría el libro "Invitación a algoritmos de parámetros fijos" de R. Niedermeier, en el que la segunda parte examina varios métodos algorítmicos.
Mathieu Chapelle
1
Vea la página de FPT Wiki para más recursos fpt.wikidot.com/books-and-survey-articles
yzll
5

Las técnicas para el diseño de algoritmos a menudo también ayudan en las reducciones. Por lo tanto, puede ser bueno aprender sobre las técnicas utilizadas para diseñar algoritmos FPT, para los cuales las notas de la Escuela de Primavera sobre Parámetros Fijos y Algoritmos Exactos (2009) pueden ser un punto de partida. En particular, es posible que desee ver las siguientes excelentes charlas generales:

Holger
fuente
3

Todavía no he tenido la oportunidad de abrirlo, pero creo que te pueden interesar los "algoritmos exponenciales exactos" de Fomin y Kratsch (del año pasado)

Aquí está su tabla de contenido:

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

Nathann

Nathann Cohen
fuente
2
Tenga en cuenta que este libro solo examina métodos algorítmicos exponenciales exactos para resolver y medir la complejidad de problemas en el punto de vista de la complejidad computacional clásica: programación dinámica, inclusión-exclusión, medir y conquistar ... No hay nada en este libro sobre ningún algoritmo método de reducción, ni en la complejidad computacional clásica ni en la complejidad parametrizada.
Mathieu Chapelle