Insieme indipendente massimale

23/10/08:

Il problema del maximal independent set (MIS). Algoritmi sequenziali per il calcolo di un MIS. Algoritmo randomizzato per il calcolo distribuito del MIS con numero di fasi O(d log n) con alta probabilità. Algoritmo di Luby randomizzato per il calcolo distribuito del MIS con numero di fasi O(log d log n) con alta probabilità.

 

Dispense: MIS.