Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2012-03-20 14:45:54.
Revizia anterioară Revizia următoare
Revizia anterioară Revizia următoare
Subarbore
La inceput se ruleaza algoritmul roy floyd pentru a determina toate drumurile posibile de cost minim si formam din ele un graf complet.
Trebuie sa selectam un arbore partial de cost minim care poate avea maxim T frunze. Acesta poate avea maxim T-2 noduri interne. Astfel noi alegem cele T noduri si pe langa ele mai luam inca T-2. Pentru toate submultimile formate din multimea celor T-2 selectate la care adaugam cele T noduri speciale facem arborele partial de cost minim pe graful complet si selectam minimul.
Complexitate: N3+(2T)*(T^2)*logT
