Libros / Notas de conferencias sobre la complejidad parametrizada

Respuestas:

23

Un buen lugar para comenzar es la "Teoría de la complejidad parametrizada" de Jörg Flum y Martin Grohe, publicada por Springer.

Adam Bouland
fuente
17

Perdón por la autopublicidad, pero esta primavera hemos estado desarrollando un curso híbrido de pregrado / posgrado en Stanford sobre algoritmos parametrizados y complejidad. Hemos tratado de "rehacer" muchas de las pruebas de los teoremas centrales en la literatura, de una manera que sea algo más accesible para los estudiantes de pregrado. Las notas del escriba están (en su mayoría) en línea . Sin embargo, no los hemos editado cuidadosamente, por lo que todavía no tomaría las notas como evangelio.

Ryan Williams
fuente
66
Las notas del escriba ya no están allí. ¿Los volverás a publicar?
Austin Buchanan
13

Daniel Marx tiene varias charlas interesantes sobre FPT y temas relacionados en su sitio web. http://www.cs.bme.hu/~dmarx/

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

Vea también la colección reciente de ensayos / libro con motivo del 60 cumpleaños de Mike Fellows. http://link.springer.com/book/10.1007/978-3-642-30891-8/page/1

Actualización (noviembre de 2014): Marek Cygan et al (larga lista de autores) tienen un libro titulado "Algoritmos parametrizados" que debería salir pronto (para ser publicado por Springer). He visto borradores y es bastante agradable. Más algorítmico que el libro de Flum-Grohe y también cubre varios desarrollos recientes.

Chandra Chekuri
fuente
7

Ver http://fpt.wikidot.com/books-and-survey-articles . También prefiero Flum y Grohe, especialmente para la parte de dureza, mientras que el libro de Niedermeier está más centrado en el lado algorítmico. Tenga en cuenta que hay algunas diferencias técnicas entre los dos, por ejemplo, la definición de un parámetro como función computable de tiempo polinomial en el libro de Flum y Grohe, que debe modificarse si a uno le gusta considerar clases espaciales parametrizadas más pequeñas (consulte este artículo por Elberfeld, Stockhusen y Tantau).

frafl
fuente
4

¿Qué pasa con el libro clásico (primero?) De 1999 sobre el tema de Rod Downey y Mike Fellows?

Hace dos años, escuché que Rod y Mike iban a sacar una segunda edición de su libro, puede que ya esté disponible. El sitio web de Mike http://www.mrfellows.net debería tener más información. Puede suscribirse a su lista de correo (boletín) que sale cada 2-3 meses.

Sameer Gupta
fuente
La segunda edición está fuera (en 2015). El nombre del libro es Fundamentals of Parameterized Complexity . Siento que este libro cubre los conceptos básicos con más detalle que el famoso libro de Flum y Grohe.
Cyriac Antony