Bücher / Vorlesungsunterlagen zur parametrisierten Komplexität

Antworten:

23

Ein guter Anfang ist "Parametrisierte Komplexitätstheorie" von Jörg Flum und Martin Grohe, herausgegeben von Springer.

Adam Bouland
quelle
17

Wir entschuldigen uns für die Eigenwerbung, aber in diesem Frühjahr haben wir in Stanford einen hybriden Bachelor- / Diplomkurs über parametrisierte Algorithmen und Komplexität entwickelt. Wir haben versucht, viele der Beweise der Kernsätze in der Literatur auf eine Weise zu "wiederholen", die für Studenten etwas zugänglicher ist. Die Schreibnotizen sind (meistens) online . Wir haben jedoch nicht alle sorgfältig bearbeitet, sodass ich die Notizen noch nicht als Evangelium ansehen würde.

Ryan Williams
quelle
6
Die Schreibnotizen sind nicht mehr da. Wirst du sie umbuchen?
Austin Buchanan
13

Daniel Marx hält auf seiner Website mehrere interessante Vorträge über FPT und verwandte Themen. http://www.cs.bme.hu/~dmarx/

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

Siehe auch die aktuelle Sammlung von Aufsätzen / Büchern zum 60. Geburtstag von Mike Fellows. http://link.springer.com/book/10.1007/978-3-642-30891-8/page/1

Update (Nov 2014): Marek Cygan et al. (Lange Autorenliste) haben ein Buch mit dem Titel "Parameterized Algorithms" herausgebracht, das in Kürze erscheinen soll (erscheint bei Springer). Ich habe Entwürfe gesehen und es ist ganz nett. Algorithmischer als das Flum-Grohe-Buch und behandelt auch einige neuere Entwicklungen.

Chandra Chekuri
quelle
7

Siehe http://fpt.wikidot.com/books-and-survey-articles . Ich bevorzuge auch Flum und Grohe, insbesondere für den Härteteil, während das Buch von Niedermeier mehr auf die algorithmische Seite konzentriert ist. Beachten Sie, dass es einige technische Unterschiede zwischen den beiden gibt, z. B. die Definition eines Parameters als polynomial time computable function im Buch von Flum und Grohe, die geändert werden muss, wenn kleinere parametrisierte Raumklassen berücksichtigt werden sollen (siehe diesen Artikel von Elberfeld, Stockhusen und Tantau).

frafl
quelle
4

Was ist mit dem klassischen (ersten?) Buch von 1999 über das Thema von Rod Downey und Mike Fellows?

Vor zwei Jahren hörte ich, dass Rod und Mike eine zweite Ausgabe ihres Buches herausbringen würden - vielleicht ist es jetzt heraus. Mikes Website http://www.mrfellows.net sollte weitere Informationen enthalten. Sie können sich für seine Mailingliste (Newsletter) anmelden, die alle 2-3 Monate erscheint.

Sameer Gupta
quelle
Die 2. Auflage ist erschienen (2015). Der Name des Buches lautet Fundamentals of Parameterized Complexity . Ich bin der Meinung, dass dieses Buch die Grundlagen ausführlicher behandelt als das berühmte Buch von Flum und Grohe.
Cyriac Antony
2

Ein relativ neues Lehrbuch stammt von Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Daniel Marx, Marcin Pilipczuk, Michał Pilipczuk und Saket Saurabh https://www.springer.com/in/book/9783319212746

Kauray
quelle