Romanian Journal of Information Technology and Automatic Control / Vol. 14, No. 3, 2004

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

Mihai Virgil Cherana

Abstract:

Î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.

Keywords:
Set maximal independent, Maximal Independent Set, algoritmi de optimizare.

View full article:

CITE THIS PAPER AS:
Mihai Virgil Cherana, "DETERMINAREA SETULUI MAXIMAL INDEPENDENT ÎNTR-O REȚEA SINCRONĂ", Romanian Journal of Information Technology and Automatic Control, ISSN 1220-1758, vol. 14(3), pp. 105-108, 2004.