Revista Română de Informatică și Automatică / Vol. 14, Nr. 3, 2004

DETERMINAREA SETULUI MAXIMAL INDEPENDENT ÎNTR-O REȚEA SINCRONĂ

Mihai Virgil Cherana

Rezumat:

În acest articol, voi prezenta un algoritm de determinare a unui set maximal independent, în cadrul unei rețele sincrone. Voi prezenta algoritmul formal, susținut de demonstrații matematice. La final, voi realiza o analiză de complexitate și de timp a acestuia. Algoritmul a fost original dezvoltat în cadrul MIT, o contribuție importantă având-o doamna Nancy Lynch, profesoară în cadrui acestei instituții. Contribuția personală a autorului este legată de demonstrația teoremei din cadrul algoritmului.

Cuvinte cheie:
Set maximal independent, Maximal Independent Set, algoritmi de optimizare.

Vizualizează articolul complet:

CITAREA ACESTUI ARTICOL SUNT URMĂTOARELE:
Mihai Virgil Cherana, „DETERMINAREA SETULUI MAXIMAL INDEPENDENT ÎNTR-O REȚEA SINCRONĂ”, Revista Română de Informatică și Automatică, ISSN 1220-1758, vol. 14(3), pp. 105-108, 2004.