h1. Tree decompositions

h1. ree decompositions

(Categoria _Algoritmi_, Autor _Marius Stroe_)

Tehnica liniarizarii arborelui nu ne este de folos in acest caz, deoarece modul de reprezentare a informatiilor nu permite obtinerea unei complexitati mai bune fata de 'solutia lenta':tree-decompositions#solutie-brute prezentata mai sus.

O solutie mai buna foloseste asa numita tehnica $longest path decomposition$, tehnica ce necesita cunostinte minime despre grafuri si cu care vom obtine complexitatea $O(M*sqrt(N)*log(N))$ urmand pasii de mai jos:

O solutie mai buna foloseste asa numita tehnica $longest path decomposition$, tehnica ce necesita cunostine minime despre grafuri si cu care vom obtine complexitatea $O(M*sqrt(N)*log(N))$ urmand pasii de mai jos:

# Se elimina cel mai lung lant radacina-frunza din arbore si se apeleaza recursiv pentru restul componentelor conexe;
# Se retine fiecare lant ca un vector <tex> Path[\ ].array[\ ] </tex> cu noduri ordonate crescator dupa adancime si se pastreaza un pointer catre nodul din lantul sau parinte <tex> Path[\ ].parent </tex>;