Μάθημα : Αποκεντρωμένος Υπολογισμός & Μοντελοποίηση

Ύλη:

Μη-Επεκτάσιμο Ανεξάρτητο σύνολο (Maximal Independent Set - MIS):

1. Απόδειξη τυχαιοκρατικού αλγορίθμου για χρωματισμό γραφημάτων
2. Βασικές έννοιες MIS
3. Ο σειριακός αλγόριθμος για MIS και μία άμεση προσαρμογή του σε κατανεμημένο περιβάλλον
4. Αδυναμία επίλυσης του MIS χωρίς τυχαιοκρατία
5. Ένας τυχαιοκρατικός αλγόριθμος για MIS

Υλικό:

Διαφάνειες

Η εγγραφή της διάλεξης σε zoom όσον αφορά το MIS

Δείτε τις αναφορές στην τελευταία διαφάνεια.

[1]  Chapter 8: Maximal Independent Set, 2016.