Des références pour les techniques de réductions FPT?

15

Comme tout le monde le sait, le célèbre livre de Garey et Johnson (et bien d'autres) fournit une excellente référence pour la technique de réduction en milieu classique. Existe-t-il des enquêtes ou des livres sur le thème de la technique de réduction dans l'algorithme paramétré, disons la réduction fpt?

cc.complexity-theory reference-request reductions parameterized-complexity Régularité
la source
1
Voir Wikipédia et ses références.
MS Dousti

Réponses:

10

Le livre original sur la complexité paramétré de Downey et Fellows , ainsi que le livre plus récent de Flum et Grohe , sont de bonnes références pour les techniques de réduction.

Suresh Venkat
la source
2
Plus précisément, le chapitre 2 de ce dernier (intitulé: «Réductions et intractabilité paramétrable») fournit une bonne enquête.
MS Dousti
3
Je citerais également le livre "Invitation to Fixed-Parameter Algorithms" de R. Niedermeier, dans lequel la deuxième partie passe en revue plusieurs méthodes algorithmiques.
Mathieu Chapelle
1
Voir la page Wiki FPT pour plus de ressources fpt.wikidot.com/books-and-survey-articles
yzll
5

Les techniques de conception d'algorithmes contribuent souvent également aux réductions. Par conséquent, il peut être bon de se renseigner sur les techniques utilisées pour concevoir des algorithmes FPT, pour lesquels les notes de la Spring School on Fixed Parameter and Exact Algorithms (2009) peuvent être un point de départ. En particulier, vous voudrez peut-être consulter les excellentes présentations suivantes:

  • Dániel Marx sur les techniques algorithmiques FPT ( slides ).
  • Thore Husfeldt sur A Taxonomic Introduction to Exact Algorithms ( slides | notes de cours ).
Holger
la source
3

Je n'ai pas encore eu l'occasion de l'ouvrir, mais je suppose que vous pourriez être intéressé par "Algorithmes exponentiels exacts" de Fomin et Kratsch (de l'année dernière)

Voici sa table des matières:

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

Nathann

Nathann Cohen
la source
2
Notez que ce livre ne passe en revue que les méthodes algorithmiques exponentielles exactes pour résoudre et mesurer la complexité des problèmes du point de vue de la complexité informatique classique: programmation dynamique, inclusion-exclusion, mesurer et conquérir, ... Il n'y a rien dans ce livre à propos de tout algorithme méthode de réduction, ni en complexité informatique classique, ni en complexité paramétrée.
Mathieu Chapelle