Vi presenterar en distribuerad algoritm som konstruerar ett O(log n)-ungefärligt minimum spanning träd (MST) i alla godtyckliga nätverk. Denna algoritm körs i tid Õ(D(G)+ L(G, w)) där L(G, w) är en parameter som kallas den kortaste lokala banans diameter och D(G) är grafens (oviktade) diameter. Vår algoritm är existentiellt optimal (upp till polylogaritmiska faktorer), d.v.s. det finns grafer som behöver.(D(G) + L(G, w)) tid för att beräkna en H - approximation till MST för alla H  på [1],  på (log n)]. Vårt resultat visar också att det kan finnas ett betydande tidsgap mellan exakt och ungefärlig MST-beräkning: det finns grafer där körtiden för vår approximationsalgoritm är exponentiellt snabbare än den tidsoptimala distribuerade algoritmen som beräknar MST. Slutligen visar vi att vår algoritm kan användas för att hitta en ungefärlig MST i trådlösa nätverk och i slumpmässiga viktade nätverk på nästan optimal Õ(D(G) tid.
Den distribuerade algoritmen för Khan och Pandurangan REF ger en O (log n)-ungefärlig MST, och är meddelandeoptimal men inte tidsoptimal.
A fast distributed approximation algorithm for minimum spanning trees
{'venue': 'Distributed Computing', 'journal': 'Distributed Computing', 'mag_field_of_study': ['Computer Science', 'Mathematics', 'Engineering']}