10 Ιουνίου - 16 Ιουνίου

Διάλεξη 10/6

Παραμετρικοί αλγόριθμοι με παράμετρο το δενδροπλάτος (treewidth) 

• Παραμετρικοί αλγόριθμοι για Independet Set και 3-Coloring με παράμετρο το treewidth. Θεώρημα Courcelle.
  Διαφάνειες (24-29) και Διαφάνειες (1-20)
• Προτεινόμενη μελέτη: [Cygan et al, Parameterized Algorithms], κεφ. 7.1-7.4

Παραμετρικές αναγωγές

• Παραμετρικές αναγωγές. Παραμετρική δυσκολία των Independent Set, Dominating set. W-hierarchy, weft.
  Διαφάνειες (1-6, 7-17 συνοπτικά)
• Προτεινόμενη μελέτη: [Cygan et al, Parameterized Algorithms], κεφ. 13.1-13.3 (συνοπτικά, ορισμούς μόνο).