Abschnitt Name Beschreibung
Vorlesungsfolien Datei 01. Vorlesung (21.04.2020): Einleitung und zwei Beispiele: TSP und MIS [Update 21.04., 10:13 auf den Stand des Videos]
Datei 01. Vorlesung (21.04.2020): Druckversion
Datei 02. Vorlesung (28.04.2020): Verzweigungsalgorithmus für k-SAT
Datei 02. Vorlesung (28.04.2020): Druckversion
Datei 03. Vorlesung (05.05.2020): Minimum Dominating Set
Datei 03. Vorlesung (05.05.2020): Druckversion
Datei 04. Vorlesung (12.05.2020): Measure & Conquer [15.5.: kleine Ergänzungen dank AE]
Datei 04. Vorlesung (12.05.2020): Druckversion
Datei 05. Vorlesung (19.05.2020): Inclusion–Exclusion [22.05.: N_0 ≠ N(∅) – Danke, FE!]
Datei 05. Vorlesung (19.05.2020): Druckversion
Datei 06. Vorlesung (26.06.2020): Graphfärben
Datei 06. Vorlesung (26.06.2020): Druckversion
Datei 07. Vorlesung (09.06.2020): Allgemeine Inclusion–Exclusion, angewandt auf Färbung
Datei 07. Vorlesung (09.06.2020): Druckversion
Datei 08. Vorlesung (16.06.2020): Teilbaumprobleme und Zerlegungsprobleme [Laufzeit DP gefixt]
Datei 08. Vorlesung (16.06.2020): Druckversion
Datei 09. Vorlesung (23.06.2020): Teil I: Fest-Parameter-Berechenbarkeit (Wiederholung AGT)
Datei 09. Vorlesung (23.06.2020): Druckversion
Datei 09. Vorlesung (23.06.2020): Teil II: Reduktionen und die W-Hierarchie
Datei 09. Vorlesung (23.06.2020): Druckversion
Datei 10. Vorlesung (30.06.2020): Kernbildung [30.6.: Bildchen für Regeln 3 und 4 hinzugefügt]
Datei 10. Vorlesung (30.06.2020): Druckversion
Datei 11. Vorlesung (07.07.2020): Alternative Parameterisierungen; Baumzerlegung [07.07., 15:50: kleine Änderungen]
Datei 11. Vorlesung (07.07.2020): Druckversion
Datei 12. Vorlesung (13.07.2020): Iterative Kompression
Datei 12. Vorlesung (13.07.2020): Druckversion
Zusätzliche Materialien Link/URL 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. 

Link/URL 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.

Link/URL Lecture 6: Independent Sets by Byskov

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

Link/URL Lecture 7: Source paper for the (R,F,O) formulation
Link/URL 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

Link/URL Lecture 8: Subtrees Problems Source Paper
Link/URL 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]. 

Link/URL Lecture 11: Channel Assignment, NP-completeness on bounded treewidth graphs
Link/URL Exercise Sheet 13: Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization
Link/URL Lecture 14: Bern's Article on Steiner Trees in Planar graphs