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

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.

URL Lecture 6: Independent Sets by Byskov

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

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

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

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