Wikipedia

Arbore minim de acoperire

Un arbore minim de acoperire sau un arbore de acoperire de pondere minimă este o submulțime a muchiilor unui graf neorientat conex cu muchii ponderate, care toate nodurile între ele, fără cicluri și cu ponderea totală a muchiilor minimă. Adică este un arbore de acoperire⁠(d) a cărui sumă a ponderilor muchiilor este cât mai mică posibil. Mai general, orice graf neorientat cu muchii ponderate (nu neapărat conex) are o pădure minimă de acoperire, care este o reuniune a arborilor minimi de acoperire ai componentelor sale conexe.

Un graf planar și arborele său minim de acoperire. Fiecare muchie este etichetată cu ponderea sa, care aici este aproximativ proporțională cu lungimea sa.

Există multe cazuri de utilizare pentru arborii minimi de acoperire. Un exemplu este o companie de telecomunicații care încearcă să întindă cabluri într-un cartier nou. Dacă este constrânsă să îngroape cablurile numai de-a lungul anumitor căi (de exemplu, străzi), atunci ar exista un graf care conține punctele (de exemplu, case) conectate de acele căi. Unele dintre căi ar putea fi mai costisitoare, deoarece sunt mai lungi sau necesită îngroparea cablului mai adânc; aceste căi ar fi reprezentate de muchii cu ponderi mai mari. Costul monetar este o unitate acceptabilă pentru ponderea muchiei — nu este nevoie ca lungimile muchiilor să respecte regulile normale de geometrie, cum ar fi inegalitatea triunghiului. Un arbore de acoperire pentru acel graf ar fi un subgrup al acelor căi care nu are cicluri, dar conectează totuși fiecare casă; ar putea exista mai mulți arbori de acoperire. Un arbore minim de acoperire ar fi unul cu cel mai mic cost total, reprezentând calea cea mai puțin costisitoare pentru așezarea cablurilor.

Proprietăți modificare

Posibilă multiplicitate modificare

Dacă există n noduri în graf, atunci fiecare arbore de acoperire are n − 1 muchii.

 
Această figură arată că poate exista mai mult de un singur arbore minim de acoperire într-un graf. În figură, cei doi arbori de sub graf sunt două variante de arbore minim de acoperire al grafului dat.

Pot exista mai mulți arbori minimi de acoperire cu aceeași pondere totală; în special, dacă toate ponderile muchiilor unui graf sunt aceleași, atunci toți arborii de acoperire ai grafului sunt și minimi.

Unicitate modificare

Dacă fiecare muchie are o pondere distinctă, atunci va exista un arbore minim de acoperire unic. Acest lucru este adevărat în multe situații realiste, cum ar fi exemplul companiei de telecomunicații de mai sus, în care este puțin probabil ca două căi să aibă exact același cost. Acest lucru se generalizează și la păduri de acoperire.

Demonstrație:

  1. Să presupunem contrariul⁠(d), că există doi AMA diferiți A și B.
  2. Deoarece A și B diferă, deși conțin aceleași noduri, există cel puțin o muchie care aparține unuia, dar nu celuilalt. Dintre astfel de muchii, fie e1 cea cu cea mai mică pondere; această alegere este unică, deoarece ponderile muchiilor sunt toate distincte. Fără pierderea generalității, să presupunem că e1 este în A.
  3. Deoarece B este un AMA, { e1 } ∪ B trebuie să conțină un ciclu C avându-l pe e1.
  4. Ca arbore, A nu conține cicluri, prin urmare C trebuie să aibă o muchie e2 care nu este în A.
  5. Din moment ce e1 a fost aleasă ca muchia unică cu cea mai mică pondere printre cele care aparțin exact unuia dintre A și B, ponderea lui e2 trebuie să fie mai mare decât ponderea lui e1.
  6. Deoarece e1 și e2 fac parte din ciclul C, înlocuirea lui e2 cu e1 în B produce un arbore de acoperire cu ponderea mai mică.
  7. Acest lucru contrazice presupunerea că B este un AMA.

Mai general, dacă ponderile muchiilor nu sunt toate distincte, atunci doar (multi-)mulțimea ponderilor din arborele minim de acoperire este cu siguranță unică; la fel pentru toți arborii minimi de acoperire.[1]

Subgraful de cost minim modificare

Dacă ponderile sunt pozitive, atunci un arbore minim de acoperire este de fapt un subgraf de cost minim care acoperă toate vârfurile, deoarece subgrafurile care conțin cicluri au obligatoriu o pondere totală mai mare decât un arbore. În schimb, dacă există ponderi negative, atunci un ciclu conținând o muchie de pondere negativă poate reduce ponderea totală a subgrafului de acoperire, și îl poate astfel face să aibă cost mai mic decât AMA.

Proprietatea de ciclu modificare

Pentru orice ciclu C din graf, dacă ponderea unei muchii e lui C este mai mare decât ponderile individuale ale tuturor celorlalte muchii ale lui C, atunci această muchie nu poate aparține unui AMA.

Demonstrație: presupunem contrariul⁠(d), adică presupunem că e aparține unui AMA T1 . Atunci, ștergerea lui e va împărți T1 în doi subarbori cu două capete ale lui e aflate în subarbori diferiți. Restul de C reconectează subarborii, prin urmare există o muchie f a lui C cu capete în subarbori diferiți, adică ea reconectează subarborii într-un arbore T2 cu pondere mai mică decât cea a lui T1, deoarece ponderea lui f este mai mică decât ponderea lui e.

Proprietatea de tăietură modificare

 
Această figură arată proprietatea de tăietură a AMA-urilor. T este singurul AMA al grafului dat. Dacă S = {A, B, D, E}, deci VS = {C, F}, atunci există 3 posibilități ale muchiei de-a lungul tăierii (S, V-S), anume muchiile BC, EC, EF ale grafului originar. Atunci, e este una dintre muchiile de pondere minimă pentru tăiere, prin urmare S ∪ {e} face parte din AMA T.

Pentru orice tăietură⁠(d) C a grafului, dacă ponderea unei muchii e în mulțimea tăieturilor lui C este strict mai mică decât ponderile tuturor celorlalte muchii din mulțimea de tăieturi ale lui C, atunci această muchie aparține tuturor AMA-urilor grafului.

Demonstrație: Presupunem că există un AMA T care nu conține e. Adăugarea lui e la T va produce deci un ciclu care traversează tăietura o dată în e și se întoarce la o altă muchie e' . Ștergând e' obținem un arbore de acoperire T∖{e'} ∪ {e} cu pondere strict mai mică decât T. Acest lucru contrazice presupunerea că T este un AMA.

Printr-un argument similar, dacă mai mult de o margine are ponderea minimă pe o tăietură, atunci fiecare astfel de muchie este conținută într-un arbore minim de acoperire.

Muchia de cost minim modificare

Dacă muchia de cost minim e a unui graf este unică, atunci această muchie este inclusă în orice AMA.

Demonstrație: dacă e nu ar fi inclus în AMA, eliminarea oricăror muchii (cu costuri mai mari) din ciclul format după adăugarea lui e la AMA, ar produce un arbore cu pondere mai mică.

Contracția modificare

Dacă T este un arbore de muchii din AMA, atunci putem contracta T într-un singur nod, menținând în același timp invariantul că AMA al grafului contractat plus T dă AMA pentru graful dinainte de contracție.[2]

Algoritmi modificare

În toți algoritmii de mai jos, m este numărul de muchii din graf și n este numărul de noduri.

Algoritmi clasici modificare

Primul algoritm pentru găsirea unui arbore minim de acoperire a fost dezvoltat de omul de știință ceh Otakar Borůvka⁠(d) în 1926 (algoritmul lui Borůvka). Scopul său era o acoperire electrică eficientă a Moraviei. Algoritmul se derulează într-o succesiune de etape. În fiecare etapă, numită pas Boruvka, el identifică o pădure F constând din muchia de pondere minimă incidentă fiecărui nod din graful G, apoi formează graful   ca intrare la pasul următor. Aici, cu   se notează graful derivat din G prin contractarea muchiilor din F (prin proprietatea de tăiere, aceste muchii aparțin AMA). Fiecare pas Boruvka necesită timp liniar. Deoarece numărul de muchii este redus cu cel puțin jumătate la fiecare pas, algoritmul lui Boruvka are complexitatea în timp O(m log n).[2]

Un al doilea algoritm este algoritmul lui Prim, care a fost inventat de Vojtěch Jarník⁠(d) în 1930 și redescoperit de Prim⁠(d) în 1957 și Dijkstra în 1959. Practic, el crește AMA (T) muchie cu muchie. Inițial, T conține un nod arbitrar. În fiecare etapă, T este mărit cu o muchie cu cea mai mică pondere (x, y) astfel încât x este în T și y nu este încă în T. Prin proprietatea de tăiere, toate muchiile adăugate la T se află în AMA. Durata sa de rulare este fie O (m log n), fie O (m + n log n), în funcție de structurile de date utilizate.

Un al treilea algoritm utilizat în mod obișnuit este algoritmul lui Kruskal, care rulează tot în timp O(m log n).

Un al patrulea algoritm, nu la fel de frecvent utilizat, este algoritmul de ștergere inversă⁠(d), care este inversul algoritmului lui Kruskal. Timpul său de rulare este O(m log n (log log n)3).

Toți acești patru sunt algoritmi greedy. Deoarece rulează în timp polinomial, problema găsirii unor astfel de arbori este în clasa de complexitate FP și problemele de decizie⁠(d) conexe, cum ar fi determinarea dacă o anumită muchie este în AMA sau determinarea dacă ponderea totală minimă depășește o anumită valoare sunt în P.

Algoritmi mai rapizi modificare

Mai mulți cercetători au încercat să găsească algoritmi mai eficienți din punct de vedere al calculului.

Într-un model comparativ, în care singurele operații permise pe ponderile muchiilor sunt comparațiile în perechi, Karger, Klein & Tarjan (1995) au găsit un algoritm randomizat în timp liniar⁠(d) bazat pe o combinație între algoritmul lui Borůvka și algoritmul de ștergere inversă.[3][4]

Cel mai rapid algoritm nerandomizat bazat pe comparații, cu complexitate cunoscută, al lui Bernard Chazelle⁠(d), se bazează pe heap-ul soft, o coadă cu prioritate aproximativă.[5][6] Durata sa de rulare este O(m α(m, n)), unde α este inversul funcțional clasic al funcției Ackermann⁠(d). Funcția α crește extrem de lent, astfel încât, în toate scopurile practice, poate fi considerată o constantă nu mai mare de 4; astfel, algoritmul lui Chazelle rulează foarte aproape de timpul liniar.

Algoritmi în timp liniar pentru cazuri speciale modificare

Grafuri dense modificare

Dacă graful este dens (adică m / n ≥ log log log n), atunci un algoritm determinist conceput de Fredman și Tarjan găsește AMA într-un timp O(m).[7] Algoritmul execută o serie de faze. Fiecare fază execută algoritmul lui Prim de multe ori, de fiecare dată pentru un număr limitat de pași. Durata fiecărei faze este O(m+n). Dacă numărul de vârfuri înainte de o fază este n', numărul de noduri rămase după o fază este cel mult m' / 2m/n' . Prin urmare, sunt necesare cel mult log* n faze, ceea ce oferă un timp de rulare liniar pentru grafuri dense.[2]

Există și alți algoritmi care funcționează în timp liniar pe grafuri dense.[5][8]

Ponderi întregi modificare

Dacă ponderile muchiilor sunt numere întregi reprezentate în binar, atunci se cunosc algoritmi determiniști care rezolvă problema în O(m + n) operații cu întregi.[9] Rămâne deschisă întrebarea dacă problema poate fi rezolvată determinist pentru un graf general în timp liniar printr-un algoritm bazat pe comparații.

Arborii de decizie modificare

Dat fiind graful G în care nodurile și muchiile sunt fixe, dar ponderile sunt necunoscute, este posibil să se construiască un arbore de decizie⁠(d) (AD) binar pentru calcularea AMA pentru orice permutare a ponderilor. Fiecare nod intern din AD conține o comparație între două muchii, de exemplu „ponderea muchiei dintre x și y este mai mare decât ponderea muchiei dintre w și z ?”. Cei doi copii ai nodului corespund celor două posibile răspunsuri „da” sau „nu”. În fiecare frunză din AD, există o listă de muchii din G care corespund unui AMA. Complexitatea de rulare a unui AD este cel mai mare număr de interogări necesare pentru a găsi AMA, care este doar adâncimea AD. Un AD pentru un graf G se numește optim dacă are cea mai mică adâncime dintre toate AD-urile corecte pentru G.

Oricare ar fi un număr întreg r, se pot găsi arbori de decizie optimi pentru toate grafurile pe r muchii prin căutarea cu forță brută⁠(d). Această căutare se desfășoară în doi pași.

A. Generarea tuturor AD potențiali

  • Sunt   grafuri diferite pe r noduri.
  • Pentru orice graf, un AMA poate fi întotdeauna găsit folosind r(r−1), de exemplu, prin algoritmul lui Prim.
  • Prin urmare, adâncimea unui AD optim este mai mică decât r2.
  • Prin urmare, numărul de noduri interne într-un AD optim este mai mic decât  .
  • Fiecare nod intern compară două muchii. Numărul muchiilor este cel mult r2 deci numărul diferit de comparații este cel mult r4.
  • Prin urmare, numărul AD-ilor potențiali este mai mic decât:   .

B. Identificarea AD-ilor corecți. Pentru a verifica dacă un AD este corect, trebuie verificat pe toate permutările posibile ale ponderilor muchiilor.

  • Numărul acestor permutări este cel mult (r2)!.
  • Pentru fiecare permutare, se rezolvă problema AMA pe graful dat folosind orice algoritm existent și se compară rezultatul cu răspunsul dat de AD.
  • Timpul de funcționare al oricărui algoritm AMA este cel mult r2, deci timpul total necesar pentru verificarea tuturor permutărilor este cel mult  .

Prin urmare, timpul total necesar pentru găsirea unui AD optim pentru toate grafurile cu r noduri este:  , care este mai mic decât:  .[2]

Algoritm optim modificare

Seth Pettie și Vijaya Ramachandran au găsit un algoritm determinist, demonstrabil optim, pe bază de comparații, pentru arborele minim de acoperire.[2] Mai jos este o descriere simplificată a algoritmului.

  1. Fie  , unde n este numărul de noduri. Se găsesc toți arborii de decizie optimi pe r noduri. Acest lucru se poate face în timp O(n).
  2. Se împarte graful în componente cu cel mult r noduri în fiecare componentă. Această partiție folosește un heap soft⁠(d), care „corupe” un număr mic de muchii ale grafului.
  3. Se utilizează arborii de decizie optimi pentru a găsi un AMA pentru subgraful necorupt din cadrul fiecărei componente.
  4. Se contractă fiecare componentă conectată parcursă de AMA la un singur nod și se aplică orice algoritm care funcționează pe grafuri dense în timp O(m) asupra contracției subgrafului necorupt.
  5. Se adaugă înapoi muchiile corupte în pădurea rezultată pentru a forma un subgraf garantat să conțină arborele minim de acoperire și mai mic cu un factor constant decât graful de pornire. Se aplică algoritmul optim recursiv pe acest graf.

Timpul de rulare al tuturor pașilor din algoritm este O(m), cu excepția pasului de utilizare a arborilor de decizie. Timpul de rulare al acestui pas este necunoscut, dar s-a dovedit că este optim — niciun algoritm nu poate performa mai bine decât arborele decizional optim. Astfel, acest algoritm are proprietatea particulară că este în demonstrabil optim, deși complexitatea sa de rulare este necunoscută.

Algoritmi paraleli și distribuiți modificare

Cercetările au luat în considerare și algoritmi paraleli pentru problema arborelui minim. Cu un număr liniar de procesoare, se poate rezolva problema în timp O(log n).[10][11] Bader & Cong (2006) demonstrează un algoritm care poate calcula AMA de 5 ori mai rapid pe 8 procesoare decât un algoritm secvențial optimizat.[12]

Alți algoritmi specializați au fost proiectați pentru calcularea arborilor minimi de acoperire ai unui graf atât de mare încât majoritatea acestuia trebuie stocată pe disc în orice moment. Acești algoritmi de stocare externă, de exemplu, așa cum sunt descriși în „Engineering an External Memory Minimum Spanning Tree Algorithm” de Roman, Dementiev și colab.,[13] pot funcționa, conform afirmațiilor autorilor, de doar 2 până la 5 ori mai lent decât un tradițional algoritm în memorie. Se bazează pe algoritmi de sortare a stocării externe⁠(d) eficiente și pe tehnici de contracție a graurilor⁠(d) pentru reducerea eficientă a dimensiunii graficului.

Problema poate fi abordată și într-o manieră distribuită. Dacă fiecare nod este considerat un computer și niciun nod nu știe nimic în afară de propriile legături conectate, se poate calcula totuși arborele minim de acoperire distribuit⁠(d).

AMA pe grafuri complete modificare

Alan M. Frieze⁠(d) a demonstrat că, dat fiind un grafic complet de n noduri, cu muchiile având ca ponderi variabile aleatoare independente distribuite identic, având funcția de distribuție F cu proprietatea că F'(0) > 0, apoi pe măsură ce n se apropie de + ∞⁠(d), se apropie de ponderea așteptată a AMA  , Unde   este funcția zeta Riemann (mai exact este   Constanta lui Apéry⁠(d)). Frieze și Steele⁠(d) au demonstrat și convergența probabilității. Svante Janson⁠(d) a demonstrat o teoremă limită centrală⁠(d) pentru ponderea AMA.

Pentru ponderi aleatorii uniforme în intervalul  , dimensiunea exactă așteptată a arborelui minim de acoperire a fost calculată pentru grafuri complete mici. [14]

Noduri Dimensiunea așteptată Dimensiunea estimată aproximativă
2 1/2 0,5
3 3/4 0,75
4 31/35 0,8857143
5 893/924 0,9664502
6 278/273 1.0183151
7 30739/29172 1,053716
8 199462271/184848378 1.0790588
9 126510063932/115228853025 1.0979027

Aplicații modificare

Arborii minimi de acoperire au aplicații directe în proiectarea rețelelor, inclusiv a rețelelor de calculatoare, de telecomunicații⁠(d), de transport⁠(d), de alimentare cu apă⁠(d) și rețele electrice (pentru care au fost inventate pentru prima dată, așa cum s-a menționat mai sus).[15] Ele sunt invocate ca subrutine în algoritmi pentru alte probleme, inclusiv în algoritmul Christofides pentru aproximarea problemei comis-voiajorului,[16] aproximând problema decupării minime multi-terminal (care este echivalentă în cazul unui singur terminal cu problema fluxului maxim⁠(d)),[17] și pentru aproximarea cuplajului perfect ponderat de cost minim.[18]

Printre alte aplicații practice bazate pe arbori minimi de acoperire se numără:

  • Taxonomia.[19]
  • Analiza de cluster: clustere de puncte în plan,[20] clustering o singură legătură (o metodă de clusterizare ierarhică),[21] clustering graf-teoretic, [22] și clusteringul datelor de exprimare genetică.[23]
  • Construirea arborilor pentru broadcast în rețele de calculatoare.[24]
  • Înregistrarea [25] și segmentarea imaginilor[26].
  • Extragerea caracteristicilor curbilinii în vederea computerizată.[27]
  • Recunoașterea scrisului de mână cu expresii matematice.[28]
  • Proiectarea circuitelor: implementarea eficientă a multiplicărilor constante multiple, așa cum se utilizează în filtrele de răspuns finit la impuls.[29]
  • Regionalizarea zonelor socio-geografice, gruparea zonelor în regiuni omogene, contigue.[30]
  • Compararea datelor ecotoxicologice.[31]
  • Observabilitate topologică în sistemele de alimentare.[32]
  • Măsurarea omogenității materialelor bidimensionale.[33]
  • Controlul procesului Minimax.[34]
  • Arborii minimi pot fi folosiți și pentru a descrie piețele financiare.[35][36] O matrice de corelație poate fi creată prin calcularea unui coeficient de corelație între oricare două acțiuni. Această matrice poate fi reprezentată topologic ca o rețea complexă și se poate construi un arbore minim care să vizualizeze relațiile.

Probleme conexe modificare

 
Arbori Steiner minimi de vârfuri de poligoane regulate cu N = 3 până la 8 laturi. Cea mai mică lungime a rețelei L pentru N > 5 este circumferința minus o latură. Pătratele reprezintă puncte Steiner.

Se cunoaște că problema găsirii arborelui Steiner⁠(d) al unei submulțimi a nodurilor, adică a unui arbore minim care acoperă submulțimea dată, este NP-completă.

O problemă asociată este ''k-''arborele minim de acoperire⁠(d) (k-AMA), care este arborele care acoperă o submulțime de k noduri din graf cu pondere minimă.

O mulțime de k-arbori minimi de acoperire este o submulțime de k arbori de acoperire (dintre toți arborii de acoperire posibili), astfel încât niciun arbore de acoperire din afara submulțimii să nu aibă o pondere mai mică.[37][38][39] (Această problemă nu are legătură cu k-arborele minim de acoperire.)

Arborele minim de acoperire euclidian⁠(d) este un arbore de acoperire al unui graf, ale cărui muchii au ponderi ce corespund distanței euclidiene între nodurile care sunt puncte în plan (sau spațiu).

Arborele de întindere minim rectiliniu⁠(d) este un arbore de acoperire al unui graf, ale cărui muchii au ponderile corespunzătoare distanței rectilinii între nodurile care sunt puncte în plan (sau spațiu).

În modelul distribuit, unde fiecare nod este considerat un computer și niciun nod nu știe nimic în afară de propriile legături conectate, se poate lua în considerare arborele minim de acoperire distribuit⁠(d). Definiția matematică a problemei este aceeași, dar există diferite abordări pentru o soluție.

Arborele minim de acoperire capacitat⁠(d) este un arbore care are un nod marcat (origine sau rădăcină) și fiecare dintre subarborii atașați nodului conține nu mai mult de un număr c de noduri. Numărul c se numește capacitatea arborelui. Rezolvarea optimă a acestei probleme este NP-hard,[40] dar euristicile bune, cum ar fi Esau-Williams și Sharma, produc soluții aproape de optim în timp polinomial.

Arborele minim de acoperire cu constrângere de grad⁠(d) este un arbore minim de acoperire în care fiecare nod este conectat la cel mult d alte noduri, pentru un anumit număr d. Cazul d = 2 este un caz special al problemei comis-voiajorului, astfel încât arborele minim de acoperire cu constrângere de grad este în general NP-hard.

Pentru grafuri orientate, problema arborelui minim de acoperire se numește problema arborescenței⁠(d) și poate fi rezolvată în timp pătratic folosind algoritmul Chu–Liu/Edmonds⁠(d).

Un arbore maxim de acoperire este un arbore cu pondere totală mai mare sau egală cu a oricărui alt arbore de acoperire. Un astfel de arbore poate fi găsit cu algoritmi precum Prim sau Kruskal după înmulțirea cu -1 a ponderilor muchiilor și rezolvarea problemei AMA pe noul graf. Un drum în arborele maxim de acoperire este cel mai larg drum⁠(d) din graf între cele două puncte finale: dintre toate drumurile posibile, maximizează ponderea muchiei cu pondere minimă.[41] Arborii maximi de acoperire găsesc aplicații în algoritmi de parsare a limbajelor naturale[42] și în algoritmi de instruire pentru câmpuri aleatorii condiționale⁠(d).

Problema AMA dinamic se referă la actualizarea unui AMA calculat anterior după o schimbare a ponderii muchiilor în graful originar sau inserarea/ștergerea unui nod.[43][44][45]

Problema arborelui minim de acoperire cu etichete este de a găsi un arbore de acoperire cu numărul minim de tipuri de etichete dacă fiecare muchie dintr-un graf este asociată cu o etichetă dintr-o mulțime finită de etichete, în loc de pondere.[46]

O muchie critică este muchia cu cea mai mar epondere dintr-un arbore de acoperire. Un arbore de acoperire este arbore minim critic de acoperire dacă graful nu conține un arbore de acoperire cu pondere mai mică a unei muchii critice. Un AMA este neapărat și un arbore minim critic de acoperire (fapt demonstrabil prin proprietatea tăieturii), dar nu și invers.[47][48]

Note modificare

  1. ^ „Do the minimum spanning trees of a weighted graph have the same number of edges with a given weight?”. cs.stackexchange.com. Accesat în . 
  2. ^ a b c d e Pettie, Seth; Ramachandran, Vijaya (), „An optimal minimum spanning tree algorithm” (PDF), Journal of the Association for Computing Machinery⁠(d), 49 (1), pp. 16–34, doi:10.1145/505241.505243, MR 2148431 .
  3. ^ Karger, David R.; Klein, Philip N.; Tarjan, Robert E. (), „A randomized linear-time algorithm to find minimum spanning trees”, Journal of the Association for Computing Machinery⁠(d), 42 (2), pp. 321–328, doi:10.1145/201019.201022, MR 1409738 
  4. ^ Pettie, Seth; Ramachandran, Vijaya (), „Minimizing randomness in minimum spanning tree, parallel connectivity, and set maxima algorithms”, Proc. 13th ACM-SIAM Symposium on Discrete Algorithms (SODA '02), San Francisco, California, pp. 713–722 .
  5. ^ a b Chazelle, Bernard (), „A minimum spanning tree algorithm with inverse-Ackermann type complexity”, Journal of the Association for Computing Machinery⁠(d), 47 (6), pp. 1028–1047, doi:10.1145/355541.355562, MR 1866456 .
  6. ^ Chazelle, Bernard (), „The soft heap: an approximate priority queue with optimal error rate” (PDF), Journal of the Association for Computing Machinery⁠(d), 47 (6), pp. 1012–1027, doi:10.1145/355541.355554, MR 1866455, arhivat din original (PDF) la , accesat în  .
  7. ^ Fredman, M. L.; Tarjan, R. E. (). „Fibonacci heaps and their uses in improved network optimization algorithms”. Journal of the ACM. 34 (3): 596. doi:10.1145/28869.28874. 
  8. ^ Gabow, H. N.; Galil, Z.; Spencer, T.; Tarjan, R. E. (). „Efficient algorithms for finding minimum spanning trees in undirected and directed graphs”. Combinatorica. 6 (2): 109. doi:10.1007/bf02579168. 
  9. ^ Fredman, M. L.; Willard, D. E. (), „Trans-dichotomous algorithms for minimum spanning trees and shortest paths”, Journal of Computer and System Sciences⁠(d), 48 (3), pp. 533–551, doi:10.1016/S0022-0000(05)80064-9, MR 1279413 .
  10. ^ Chong, Ka Wong; Han, Yijie; Lam, Tak Wah (), „Concurrent threads and optimal parallel minimum spanning trees algorithm”, Journal of the Association for Computing Machinery⁠(d), 48 (2), pp. 297–323, doi:10.1145/375827.375847, MR 1868718 .
  11. ^ Pettie, Seth; Ramachandran, Vijaya (), „A randomized time-work optimal parallel algorithm for finding a minimum spanning forest” (PDF), SIAM Journal on Computing⁠(d), 31 (6), pp. 1879–1895, doi:10.1137/S0097539700371065, MR 1954882 .
  12. ^ Bader, David A.; Cong, Guojing (), „Fast shared-memory algorithms for computing the minimum spanning forest of sparse graphs”, Journal of Parallel and Distributed Computing, 66 (11), pp. 1366–1378, doi:10.1016/j.jpdc.2006.06.001 .
  13. ^ Dementiev, Roman; Sanders, Peter; Schultes, Dominik; Sibeyn, Jop F. (), „Engineering an external memory minimum spanning tree algorithm”, Proc. IFIP 18th World Computer Congress, TC1 3rd International Conference on Theoretical Computer Science (TCS2004) (PDF), pp. 195–208, arhivat din original (PDF) la , accesat în  .
  14. ^ Steele, J. Michael (), „Minimal spanning trees for graphs with random edge lengths”, Mathematics and computer science, II (Versailles, 2002), Trends Math., Basel: Birkhäuser, pp. 223–245, MR 1940139 
  15. ^ Graham, R. L.; Hell, Pavol (), „On the history of the minimum spanning tree problem”, Annals of the History of Computing, 7 (1), pp. 43–57, doi:10.1109/MAHC.1985.10011, MR 0783327 
  16. ^ Nicos Christofides, Worst-case analysis of a new heuristic for the travelling salesman problem Arhivat în , la Wayback Machine., Report 388, Graduate School of Industrial Administration, CMU, 1976.
  17. ^ Dahlhaus, E.; Johnson, D. S.; Papadimitriou, C. H.; Seymour, P. D.; Yannakakis, M. (august 1994). „The complexity of multiterminal cuts” (PDF). SIAM Journal on Computing⁠(d). 23 (4): 864–894. doi:10.1137/S0097539792225297. Arhivat din original (PDF) la . Accesat în . 
  18. ^ Supowit, Kenneth J.; Plaisted, David A.; Reingold, Edward M. (). Heuristics for weighted perfect matching. 12th Annual ACM Symposium on Theory of Computing (STOC '80). New York, NY, USA: ACM. pp. 398–419. doi:10.1145/800141.804689. 
  19. ^ Sneath, P. H. A. (). „The Application of Computers to Taxonomy”. Journal of General Microbiology. 17 (1): 201–226. doi:10.1099/00221287-17-1-201. PMID 13475686. 
  20. ^ Asano, T.; Bhattacharya, B.; Keil, M.; Yao, F. (). Clustering algorithms based on minimum and maximum spanning trees. Fourth Annual Symposium on Computational Geometry (SCG '88). 1. pp. 252–257. doi:10.1145/73393.73419. 
  21. ^ Gower, J. C.; Ross, G. J. S. (). „Minimum Spanning Trees and Single Linkage Cluster Analysis”. Journal of the Royal Statistical Society. C (Applied Statistics). 18 (1): 54–64. doi:10.2307/2346439. JSTOR 2346439. 
  22. ^ Päivinen, Niina (). „Clustering with a minimum spanning tree of scale-free-like structure”. Pattern Recognition Letters. 26 (7): 921–930. doi:10.1016/j.patrec.2004.09.039. 
  23. ^ Xu, Y.; Olman, V.; Xu, D. (). „Clustering gene expression data using a graph-theoretic approach: an application of minimum spanning trees”. Bioinformatics. 18 (4): 536–545. doi:10.1093/bioinformatics/18.4.536. PMID 12016051. 
  24. ^ Dalal, Yogen K.; Metcalfe, Robert M. (). „Reverse path forwarding of broadcast packets”. Communications of the ACM. 21 (12): 1040–1048. doi:10.1145/359657.359665. 
  25. ^ Ma, B.; Hero, A.; Gorman, J.; Michel, O. (). Image registration with minimum spanning tree algorithm (PDF). International Conference on Image Processing. 1. pp. 481–484. doi:10.1109/ICIP.2000.901000. 
  26. ^ P. Felzenszwalb, D. Huttenlocher: Efficient Graph-Based Image Segmentation. IJCV 59(2) (September 2004)
  27. ^ Suk, Minsoo; Song, Ohyoung (). „Curvilinear feature extraction using minimum spanning trees”. Computer Vision, Graphics, and Image Processing. 26 (3): 400–411. doi:10.1016/0734-189X(84)90221-4. 
  28. ^ Tapia, Ernesto; Rojas, Raúl (). „Recognition of On-line Handwritten Mathematical Expressions Using a Minimum Spanning Tree Construction and Symbol Dominance” (PDF). Graphics Recognition. Recent Advances and Perspectives. Lecture Notes in Computer Science. 3088. Berlin Heidelberg: Springer-Verlag. pp. 329–340. ISBN 978-3540224785. 
  29. ^ Ohlsson, H. (). Implementation of low complexity FIR filters using a minimum spanning tree. 12th IEEE Mediterranean Electrotechnical Conference (MELECON 2004). 1. pp. 261–264. doi:10.1109/MELCON.2004.1346826. 
  30. ^ Assunção, R. M.; M. C. Neves; G. Câmara; C. Da Costa Freitas (). „Efficient regionalization techniques for socio‐economic geographical units using minimum spanning trees”. International Journal of Geographical Information Science. 20 (7): 797–811. doi:10.1080/13658810600665111. 
  31. ^ Devillers, J.; Dore, J.C. (). „Heuristic potency of the minimum spanning tree (MST) method in toxicology”. Ecotoxicology and Environmental Safety. 17 (2): 227–235. doi:10.1016/0147-6513(89)90042-0. PMID 2737116. 
  32. ^ Mori, H.; Tsuzuki, S. (). „A fast method for topological observability analysis using a minimum spanning tree technique”. IEEE Transactions on Power Systems. 6 (2): 491–500. Bibcode:1991ITPSy...6..491M. doi:10.1109/59.76691. 
  33. ^ Filliben, James J.; Kafadar, Karen; Shier, Douglas R. (). „Testing for homogeneity of two-dimensional surfaces”. Mathematical Modelling. 4 (2): 167–189. doi:10.1016/0270-0255(83)90026-X. 
  34. ^ Kalaba, Robert E. (), Graph Theory and Automatic Control (PDF), arhivat din original (PDF) la , accesat în  
  35. ^ Mantegna, R. N. (1999). Hierarchical structure in financial markets. The European Physical Journal B-Condensed Matter and Complex Systems, 11(1), 193-197.
  36. ^ Djauhari, M., & Gan, S. (2015). Optimality problem of network topology in stocks market analysis. Physica A: Statistical Mechanics and Its Applications, 419, 108-114.
  37. ^ Gabow, Harold N. (), „Two algorithms for generating weighted spanning trees in order”, SIAM Journal on Computing⁠(d), 6 (1), pp. 139–150, doi:10.1137/0206011, MR 0441784 .
  38. ^ Eppstein, David (), „Finding the k smallest spanning trees”, BIT, 32 (2), pp. 237–248, doi:10.1007/BF01994879, MR 1172188 .
  39. ^ Frederickson, Greg N. (), „Ambivalent data structures for dynamic 2-edge-connectivity and k smallest spanning trees”, SIAM Journal on Computing⁠(d), 26 (2), pp. 484–538, doi:10.1137/S0097539792226825, MR 1438526 .
  40. ^ Jothi, Raja; Raghavachari, Balaji (), „Approximation Algorithms for the Capacitated Minimum Spanning Tree Problem and Its Variants in Network Design”, ACM Trans. Algorithms, 1 (2), pp. 265–282, doi:10.1145/1103963.1103967 
  41. ^ Hu, T. C. (), „The maximum capacity route problem”, Operations Research, 9 (6), pp. 898–900, doi:10.1287/opre.9.6.898, JSTOR 167055 .
  42. ^ McDonald, Ryan; Pereira, Fernando; Ribarov, Kiril; Hajič, Jan (). „Non-projective dependency parsing using spanning tree algorithms” (PDF). Proc. HLT/EMNLP. Arhivat din original (PDF) la . Accesat în . 
  43. ^ Spira, P. M.; Pan, A. (), „On finding and updating spanning trees and shortest paths” (PDF), SIAM Journal on Computing, 4 (3), pp. 375–380, doi:10.1137/0204032, MR 0378466 .
  44. ^ Holm, Jacob; de Lichtenberg, Kristian; Thorup, Mikkel (), „Poly-logarithmic deterministic fully dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity”, Journal of the Association for Computing Machinery⁠(d), 48 (4), pp. 723–760, doi:10.1145/502090.502095, MR 2144928 .
  45. ^ Chin, F.; Houck, D. (), „Algorithms for updating minimal spanning trees”, Journal of Computer and System Sciences⁠(d), 16 (3), pp. 333–344, doi:10.1016/0022-0000(78)90022-3 .
  46. ^ Chang, R.S.; Leu, S.J. (), „The minimum labeling spanning trees”, Information Processing Letters⁠(d), 63 (5), pp. 277–282, doi:10.1016/s0020-0190(97)00127-0 .
  47. ^ „Everything about Bottleneck Spanning Tree”. flashing-thoughts.blogspot.ru. Accesat în . 
  48. ^ http://pages.cpsc.ucalgary.ca/~dcatalin/413/t4.pdf

Lecturi suplimentare modificare

Legături externe modificare

Adus de la https://ro.wikipedia.org/w/index.php?title=Arbore_minim_de_acoperire&oldid=16217890