Czy są jakieś odniesienia do technik redukcji FPT?

15

Jak wszyscy wiedzą, słynna książka Garey i Johnsona (i wiele innych) stanowi doskonałe odniesienie do techniki redukcji w scenerii klasycznej. Czy są jakieś ankiety lub książki na temat techniki redukcji w sparametryzowanym algorytmie, powiedzmy redukcja fpt?

cc.complexity-theory reference-request reductions parameterized-complexity Prawidłowość
źródło
1
Zobacz Wikipedię i jej odniesienia.
MS Dousti

Odpowiedzi:

10

Zarówno oryginalna książka o parametrach złożoności Downey i Fellows , jak i nowsza książka Fluma i Grohe są dobrymi referencjami dla technik redukcji.

Suresh Venkat
źródło
2
W szczególności rozdział 2 tego ostatniego (zatytułowany: „Ograniczenia i sparametryzowana nietykalność”) zapewnia dobrą ankietę.
MS Dousti
3
Przywołałbym także książkę „Zaproszenie do algorytmów o ustalonych parametrach” R. Niedermeiera, w której druga część analizuje kilka metod algorytmicznych.
Mathieu Chapelle,
1
Zobacz stronę FPT Wiki, aby uzyskać więcej zasobów fpt.wikidot.com/books-and-survey-articles
yzll
5

Techniki projektowania algorytmów często pomagają również w redukcji. Dlatego dobrze jest poznać techniki stosowane w projektowaniu algorytmów FPT, dla których notatki ze Szkoły wiosennej na temat stałych parametrów i dokładnych algorytmów (2009) mogą być punktem wyjścia. W szczególności warto przyjrzeć się następującym doskonałym omówieniom:

  • Dániel Marks o technikach algorytmicznych FPT ( slajdy ).
  • Thore Husfeldt o taksonomicznym wprowadzeniu do dokładnych algorytmów ( slajdy | notatki z wykładów ).
Holger
źródło
3

Nie miałem jeszcze okazji go otworzyć, ale myślę, że możesz być zainteresowany „Dokładnymi algorytmami wykładniczymi” Fomin i Kratsch (z zeszłego roku)

Oto spis treści:

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

Nathann

Nathann Cohen
źródło
2
Zauważ, że ta książka bada tylko dokładne wykładnicze metody algorytmiczne do rozwiązywania i pomiaru złożoności problemów z punktu widzenia klasycznej złożoności obliczeniowej: programowanie dynamiczne, wykluczanie włączenia, pomiar i podbijanie ... W tej książce nie ma nic na temat algorytmiki metoda redukcji, ani w klasycznej złożoności obliczeniowej, ani w sparametryzowanej złożoności.
Mathieu Chapelle,