Section outline

  • 29/5: Παραμετρικοί αλγόριθμοι δενδροπλάτους (treewidth) - παραμετρικές αναγωγές

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

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