Pagini recente » Roy-Floyd | Diferente pentru problema/expand intre reviziile 61 si 62 | Atasamentele paginii Branza | Monitorul de evaluare | Diferente pentru tree-decompositions intre reviziile 87 si 91
Nu exista diferente intre titluri.
Diferente intre continut:
seq[seq_len] = value[x]
firstPos[x] = seq_len
pentru fiecare fiu y al lui x executa
pentru fiecare fiu nevizitat y al lui x executa
PARCURGE(y) // apeleaza recursiv pentru y
sfarsit pentru
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 cunostine 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 cunostinte 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>;
Nu exista diferente intre securitate.
Topicul de forum nu a fost schimbat.