Тема Название Описание
Vorlesungsfolien Файл 01. Vorlesung (21.04.2020): Einleitung und zwei Beispiele: TSP und MIS [Update 21.04., 10:13 auf den Stand des Videos]
Файл 01. Vorlesung (21.04.2020): Druckversion
Файл 02. Vorlesung (28.04.2020): Verzweigungsalgorithmus für k-SAT
Файл 02. Vorlesung (28.04.2020): Druckversion
Файл 03. Vorlesung (05.05.2020): Minimum Dominating Set
Файл 03. Vorlesung (05.05.2020): Druckversion
Файл 04. Vorlesung (12.05.2020): Measure & Conquer [15.5.: kleine Ergänzungen dank AE]
Файл 04. Vorlesung (12.05.2020): Druckversion
Файл 05. Vorlesung (19.05.2020): Inclusion–Exclusion [22.05.: N_0 ≠ N(∅) – Danke, FE!]
Файл 05. Vorlesung (19.05.2020): Druckversion
Файл 06. Vorlesung (26.06.2020): Graphfärben
Файл 06. Vorlesung (26.06.2020): Druckversion
Файл 07. Vorlesung (09.06.2020): Allgemeine Inclusion–Exclusion, angewandt auf Färbung
Файл 07. Vorlesung (09.06.2020): Druckversion
Файл 08. Vorlesung (16.06.2020): Teilbaumprobleme und Zerlegungsprobleme [Laufzeit DP gefixt]
Файл 08. Vorlesung (16.06.2020): Druckversion
Файл 09. Vorlesung (23.06.2020): Teil I: Fest-Parameter-Berechenbarkeit (Wiederholung AGT)
Файл 09. Vorlesung (23.06.2020): Druckversion
Файл 09. Vorlesung (23.06.2020): Teil II: Reduktionen und die W-Hierarchie
Файл 09. Vorlesung (23.06.2020): Druckversion
Файл 10. Vorlesung (30.06.2020): Kernbildung [30.6.: Bildchen für Regeln 3 und 4 hinzugefügt]
Файл 10. Vorlesung (30.06.2020): Druckversion
Файл 11. Vorlesung (07.07.2020): Alternative Parameterisierungen; Baumzerlegung [07.07., 15:50: kleine Änderungen]
Файл 11. Vorlesung (07.07.2020): Druckversion
Файл 12. Vorlesung (13.07.2020): Iterative Kompression
Файл 12. Vorlesung (13.07.2020): Druckversion
Zusätzliche Materialien Гиперссылка Lecture 2: Solving SAT by branching (source paper)

This is the original paper giving the two branching algorithms for satisfiability as discussed in the lecture. 

Гиперссылка Lecture 4 supplemental: Quasiconvex analysis of multivariate recurrence equations for backtracking algorithms (by D. Eppstein)

Source paper for the quasi-convex optimization used to determine the parameters as in the last slide.

Гиперссылка Lecture 6: Independent Sets by Byskov

This is the source paper for counting cardinality-k independent sets. 

Гиперссылка Lecture 7: Source paper for the (R,F,O) formulation
Гиперссылка Lecture 7: Counting 2-Sat solutions --- Fürer & Kasiviswanathan article

Official link: 

https://link.springer.com/chapter/10.1007/978-3-540-72870-2_5

Гиперссылка Lecture 8: Subtrees Problems Source Paper
Гиперссылка Lecture 9: source paper -- W[1]-completeness of Indep. Set

This is the source paper establishing the completeness for Independent Set in the complexity class W[1]. 

Гиперссылка Lecture 11: Channel Assignment, NP-completeness on bounded treewidth graphs
Гиперссылка Exercise Sheet 13: Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization
Гиперссылка Lecture 14: Bern's Article on Steiner Trees in Planar graphs