Adakah referensi untuk teknik dalam pengurangan FPT?

15

Seperti semua orang tahu, buku terkenal Garey dan Johnson (dan banyak lainnya) memberikan referensi yang sangat baik untuk teknik reduksi dalam pengaturan klasik. Apakah ada survei atau buku tentang topik teknik reduksi dalam algoritma parameter, katakanlah pengurangan fpt?

cc.complexity-theory reference-request reductions parameterized-complexity Keteraturan
sumber
1
Lihat Wikipedia dan rujukannya.
MS Dousti

Jawaban:

10

Baik buku kompleksitas parametrized asli oleh Downey dan Fellows , dan buku baru oleh Flum dan Grohe , adalah referensi yang baik untuk teknik reduksi.

Suresh Venkat
sumber
2
Secara khusus, bab 2 dari yang terakhir (berjudul: "Reduksi dan Parameter Yang Dapat Diurangkan") menyediakan survei yang baik.
MS Dousti
3
Saya juga akan mengutip buku "Invitation to Fixed-Parameter Algorithms" oleh R. Niedermeier, di mana bagian kedua mensurvei beberapa metode algoritmik.
Mathieu Chapelle
1
Lihat halaman Wiki FPT untuk sumber lebih lanjut fpt.wikidot.com/books-and-survey-articles
yzll
5

Teknik untuk desain algoritma sering membantu dalam pengurangan juga. Oleh karena itu mungkin baik untuk belajar tentang teknik yang digunakan untuk merancang algoritma FPT, yang mana catatan Sekolah Musim Semi pada Parameter Tetap dan Algoritma Tepat (2009) dapat menjadi titik awal. Secara khusus, Anda mungkin ingin melihat ceramah ikhtisar yang sangat baik berikut:

  • Dániel Marx tentang teknik algoritme FPT ( slide ).
  • Thore Husfeldt tentang Pengantar Taksonomi untuk Algoritma Tepat ( slide | catatan kuliah ).
Holger
sumber
3

Saya belum memiliki kesempatan untuk membukanya, tapi saya kira Anda mungkin tertarik pada "Algoritma eksponensial eksak" oleh Fomin dan Kratsch (dari tahun lalu)

Ini dia daftar isinya:

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

Nathann

Nathann Cohen
sumber
2
Perhatikan bahwa buku ini hanya mensurvei metode algoritme eksponensial yang tepat untuk menyelesaikan dan mengukur kerumitan masalah dalam sudut pandang kompleksitas komputasi klasik: pemrograman dinamis, inklusi-pengecualian, ukur dan taklukkan, ... Tidak ada dalam buku ini tentang algoritmik apa pun metode reduksi, baik dalam kompleksitas komputasi klasik maupun dalam kompleksitas parameter.
Mathieu Chapelle