Buku / Catatan Kuliah tentang Kompleksitas Parametrized

Jawaban:

23

Tempat yang baik untuk memulai adalah "Parameterized Complexity Theory" oleh Jörg Flum dan Martin Grohe, yang diterbitkan oleh Springer.

Adam Bouland
sumber
17

Maaf untuk iklan-sendiri, tetapi musim semi ini kami telah mengembangkan program sarjana / pascasarjana hybrid di Stanford tentang Parameterisasi Algoritma dan Kompleksitas. Kami telah mencoba untuk "melakukan kembali" banyak bukti dari teorema inti dalam literatur, dengan cara yang agak lebih mudah diakses oleh mahasiswa sarjana. Catatan juru tulis (sebagian besar) online . Namun kami belum mengedit semuanya dengan hati-hati, jadi saya belum akan mencatatnya sebagai Injil.

Ryan Williams
sumber
6
Catatan juru tulis sudah tidak ada lagi. Apakah Anda akan memposting ulang?
Austin Buchanan
13

Daniel Marx memiliki beberapa pembicaraan menarik tentang FPT dan topik terkait di situs webnya. http://www.cs.bme.hu/~dmarx/

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

Lihat juga koleksi esai / buku terbaru pada kesempatan ulang tahun ke-60 Mike Fellows. http://link.springer.com/book/10.1007/978-3-642-30891-8/page/1

Pembaruan (Nov 2014): Marek Cygan et al (daftar panjang penulis) memiliki buku berjudul "Parameterized Algorithms" yang harus segera keluar (akan diterbitkan oleh Springer). Saya telah melihat draft dan itu cukup bagus. Lebih algoritmik daripada buku Flum-Grohe dan juga mencakup beberapa perkembangan terakhir.

Chandra Chekuri
sumber
7

Lihat http://fpt.wikidot.com/books-and-survey-articles . Saya juga lebih suka Flum dan Grohe, terutama untuk bagian kekerasan, sedangkan buku karya Niedermeier lebih fokus pada sisi algoritmik. Perhatikan bahwa ada beberapa perbedaan teknis antara keduanya, misalnya definisi parameter sebagai fungsi komputasi waktu polinomial dalam buku Flum dan Grohe, yang harus diubah jika seseorang suka mempertimbangkan kelas ruang parameter yang lebih kecil (lihat artikel ini oleh Elberfeld, Stockhusen dan Tantau).

frafl
sumber
4

Bagaimana dengan buku klasik (pertama?) Tahun 1999 tentang topik karya Rod Downey dan Mike Fellows?

Dua tahun lalu, saya mendengar bahwa Rod dan Mike akan mengeluarkan edisi kedua buku mereka - mungkin sudah keluar sekarang. Situs web Mike http://www.mrfellows.net seharusnya memiliki lebih banyak info. Anda dapat mendaftar untuk menerima milisnya (buletin) yang terbit setiap 2-3 bulan.

Sameer Gupta
sumber
Edisi ke-2 habis (tahun 2015). Nama buku adalah Fundamentals of Parameterized Complexity . Saya merasa bahwa buku ini membahas dasar-dasar lebih detail daripada buku terkenal Flum dan Grohe.
Cyriac Antony
2

Buku teks yang relatif baru adalah oleh Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, dan Saket Saurabh https://www.springer.com/in/book/9783319212746

kauray
sumber