Αποκεντρωμένος Υπολογισμός & Μοντελοποίηση (CEID_NE589)

Ύλη:

Μέγιστο Ανεξάρτητο σύνολο (Maximal Independent Set - MIS):

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

Υλικό:

Διαφάνειες

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

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

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