Abstrakt. Vi presenterar en probabilistisk algoritm som, med tanke på en ansluten graf G (representerad av adjacency listor) av genomsnittlig grad d, med kantvikter i uppsättningen {1,..., w}, och ges en parameter 0 < ε < 1/2, uppskattningar i tid O(dwε −2 log dw ε ) vikten av minsta spanning träd (MST) av G med en relativ fel av som mest ε. Observera att körtiden inte beror på antalet hörn i G. Vi visar också en nästan matchande lägre gräns av  och.(dwε −2 ) på sonden och tid komplexitet av någon approximation algoritm för MST vikt. Faktorerna. Våra anslutna komponenter algoritm plockar O(1/ε 2 ) hörn i grafen och sedan växer "lokala spännträd" vars storlekar anges av en stokastisk process. Med hjälp av den lokala information som samlas in på detta sätt kan algoritmen, med stort förtroende, dra en uppskattning av antalet anslutna komponenter. Vi visar sedan hur uppskattningar av antalet komponenter i olika delgrafer av G kan användas för att uppskatta vikten av dess MST.
Sublinjära tidsalgoritmer för uppskattning av antalet anslutna komponenter och vikten av MST gavs först av Chazelle et al. Hoppa över det.
Approximating the Minimum Spanning Tree Weight in Sublinear Time
{'venue': 'SIAM J. Comput.', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}