Chciałbym dowiedzieć się o złożoności parametryzowanej (zarówno po stronie algorytmicznej, jak i po stronie twardości). Jakie książki / notatki z wykładów mogę przeczytać na ten temat?
Chciałbym dowiedzieć się o złożoności parametryzowanej (zarówno po stronie algorytmicznej, jak i po stronie twardości). Jakie książki / notatki z wykładów mogę przeczytać na ten temat?
Odpowiedzi:
Dobrym miejscem na początek jest „Sparametryzowana teoria złożoności” Jörga Fluma i Martina Grohe, opublikowana przez Springera.
Przepraszamy za autoreklamę, ale tej wiosny opracowaliśmy hybrydowy kurs licencjacki / grad w Stanford na temat sparametryzowanych algorytmów i złożoności. Próbowaliśmy „przerobić” wiele dowodów podstawowych twierdzeń w literaturze, w sposób nieco bardziej dostępny dla studentów. Notatniki są (głównie) online . Jednak nie zredagowaliśmy ich wszystkich starannie, więc nie zapisałbym jeszcze notatek jako ewangelii.
Daniel Marx ma kilka interesujących rozmów na temat FPT i pokrewnych tematów na swojej stronie internetowej. http://www.cs.bme.hu/~dmarx/
http://www.cs.bme.hu/~dmarx/talk.php
Zobacz także najnowszą kolekcję esejów / książek z okazji 60. urodzin Mike'a Fellowsa. http://link.springer.com/book/10.1007/978-3-642-30891-8/page/1
Aktualizacja (listopad 2014 r.): Marek Cygan i wsp. (Długa lista autorów) mają książkę zatytułowaną „Sparametryzowane algorytmy”, która ukaże się wkrótce (zostanie wydana przez Springera). Widziałem przeciągi i jest całkiem fajny. Bardziej algorytmiczny niż książka Flum-Grohe, a także obejmuje kilka ostatnich zmian.
Zobacz http://fpt.wikidot.com/books-and-survey-articles . Wolę także Fluma i Grohe, szczególnie w części dotyczącej twardości, podczas gdy książka Niedermeiera bardziej skupia się na stronie algorytmicznej. Zauważ, że istnieją między nimi pewne techniczne różnice, na przykład definicja parametru jako funkcji wielomianowego obliczania czasu w Księdze Fluma i Grohe, która musi zostać zmieniona, jeśli ktoś chce rozważyć mniejsze sparametryzowane klasy przestrzeni (patrz ten artykuł : Elberfeld, Stockhusen i Tantau).
Co powiesz na klasyczną (pierwszą?) Książkę z 1999 roku autorstwa Rod Downeya i Mike'a Fellowsa na ten temat?
Dwa lata temu usłyszałem, że Rod i Mike zamierzają wydać drugie wydanie swojej książki - być może jest już dostępne. Strona Mike'a http://www.mrfellows.net powinna mieć więcej informacji. Możesz zapisać się na jego listę mailingową (newsletter), która wychodzi co 2-3 miesiące.
Stosunkowo nowym podręcznikiem jest Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk i Saket Saurabh https://www.springer.com/in/book/9783319212746
Algorytmy sparametryzowane przez Cygan i in. glin. to fajny podręcznik.
https://www.mimuw.edu.pl/~malcin/book/parameterized-alameterms.pdf