Gibt es Referenzen für Techniken zur FPT-Reduktion?

15

Wie jeder weiß, bietet das berühmte Buch von Garey und Johnson (und viele andere) eine hervorragende Referenz für die Reduktionstechnik in klassischer Umgebung. Gibt es Umfragen oder Bücher zum Thema Reduktionstechnik in parametrisierten Algorithmen, etwa zur fpt-Reduktion?

cc.complexity-theory reference-request reductions parameterized-complexity Regelmäßigkeit
quelle
1
Siehe Wikipedia und deren Referenzen.
MS Dousti

Antworten:

10

Sowohl das ursprüngliche parametrisierte Komplexitätsbuch von Downey und Fellows als auch das neuere Buch von Flum und Grohe sind gute Referenzen für Reduktionstechniken.

Suresh Venkat
quelle
2
Insbesondere Kapitel 2 der letzteren (mit dem Titel "Reduktionen und parametrisierte Intraktierbarkeit") bietet eine gute Übersicht.
MS Dousti
3
Ich würde auch das Buch "Einladung zu Algorithmen mit festen Parametern" von R. Niedermeier zitieren , in dem der zweite Teil mehrere algorithmische Methoden behandelt.
Mathieu Chapelle
1
Weitere Ressourcen finden
yzll
5

Techniken für den Entwurf von Algorithmen helfen oft auch bei der Reduktion. Deshalb kann es gut sein , um Techniken zu erlernen verwendet FPT - Algorithmen zu entwerfen, für die die Noten der Spring School auf Fixed Parameter und Algorithmen Exact (2009) kann ein Ausgangspunkt sein. Insbesondere möchten Sie vielleicht die folgenden hervorragenden Übersichtsvorträge ansehen:

  • Dániel Marx über algorithmische FPT-Techniken ( Folien ).
  • Thore Husfeldt über eine taxonomische Einführung in exakte Algorithmen ( Folien | Skript ).
Holger
quelle
3

Ich hatte noch keine Gelegenheit, es zu öffnen, aber ich vermute, Sie interessieren sich für "Exakte Exponentialalgorithmen" von Fomin und Kratsch (aus dem letzten Jahr).

Hier ist sein Inhaltsverzeichnis:

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

Nathann

Nathann Cohen
quelle
2
Beachten Sie, dass dieses Buch nur exakte exponentielle algorithmische Methoden zum Lösen und Messen der Komplexität von Problemen unter dem Gesichtspunkt der klassischen rechnerischen Komplexität untersucht: dynamische Programmierung, Einschluss-Ausschluss, Messen und Erobern, ... In diesem Buch gibt es nichts über algorithmische Methoden Reduktionsmethode, weder bei klassischer rechnerischer Komplexität noch bei parametrisierter Komplexität.
Mathieu Chapelle