Voi prezenta intr-un mod indirect cum se ajunge la aceasta complexitate, intrucat exista o solutie relativ asemanatoare celei pe care mi-am propus sa o prezint, insa nu la fel de rapida, numita _longest path decomposition_. Si, desigur, nu este rau daca stim ceva in plus. :)

Tehnica liniarizarii arborelui nu poate functiona, deoarece informatiile ce le putem retine nu ne pot permite sa obtinem o complexitate mai buna.

Tehnica liniarizarii arborelui nu poate functiona, deoarece informatiile pe care le putem retine nu ne pot permite sa obtinem o complexitate mai buna.

Insa, cu _longest path_decomposition_, tehnica ce necesita cunostine minime despre grafuri, vom obtine complexitatea $O(M*sqrt(N)*log(N))$ urmand pasii de mai jos:

Este evident ca memoria ocupata este $O(N)$, fiecare nod fiind inclus intr-un singur lant. Numarul maxim de lanturi prin care putem trece pornind din radacina pana intr-una din frunze, este $O(sqrt(N))$.

_Fig. 2 : Cazul defavorabil cand sunt $O(sqrt(N))$ lanturi elementare._
 

!heavy-path-decomposition?Figura2.jpg!