Σημειώσεις:Προβλήματα:Maximal Independent Set
Από DistrSys
| MIS |
| Πρόβλημα: Κατανεμημένες Δομές Δίκτυο: Γενικό Κλάση: - |
|
|
| Πολυπλοκότητα |
| Χρονική: O(nlogn) Επικοινωνίας: - |
|
|
| Στη σύνταξη του κειμένου συνεισέφεραν οι Απόστολος Φίλιππας Βασίλειος Γεωργιτζίκης |
Maximal Independent Set
Το Maximal Independent Set πρόβλημα έχει να κάνει με την αναζήτηση ενός MIS (βέλτιστο ανεξάρτητο σετ) από κόμβους ενός μή κατευθυντικού γράφου. Ένα σετ απο κόμβους λέγεται ανεξάρτητο όταν δεν περιέχει κανένα ζεύγος γειτονικών κόμβων, και ένα ανεξάρτητο σετ θεωρείται βέλτιστο όταν δεν μπορεί να αυξηθεί ώστε να δημιουργηθεί ένα μεγαλύτερο independent set με την πρόσθεση κόμβων. Αξίζει να σημειωθεί ότι σε έναν γράφο μπορεί να υπάρχουν πολλά διαφορετικά MIS. Δεν ζητούμε το μεγαλύτερο MIS του γράφου, αλλά οποιοδήποτε MIS μας αρκεί.
Έστω G=(V,E) ένας μή κατευθυντικός γράφος. Ένα σετ 
από κόμβους λέγεται independent όταν για όλους τους κόμβους 
. Ένα independent set I είναι και maximal όταν κανένα σετ I' που περιέχει το I δεν είναι independent. Ο στόχος μας είναι να υπολογίσουμε ένα MIS του G. Πιο συγκεκριμένα, κάθε process του οποίου το index είναι στο I τελικά πρέπει να έχει ως έξοδο winner, δηλαδή θα πρέπει να θέσει μια ειδική μεταβλητή status στη τιμή 'winner'. και όλες οι διεργασίες που δεν είναι στο I θα πρέπει να έχει έξοδο loser.
Θεωρούμε ότι το n, δηλαδή ο αριθμός των κόμβων, είναι γνωστός σε όλες τις διεργασίες. Εναλλακτικά θα μπορούσαμε να θέσουμε ένα upper bound στο n. Δεν υποθέτουμε την ύπαρξη UIDs.
