Vi använder det nyligen införda ramverket för rådgivning för att mäta svårigheten att lokalt beräkna ett minimispannträd (MST). Ett (m, t)-anvisningsschema för ett distribuerat problem P är ett sätt, för varje möjlig inmatning I av P, att ge en "rådgivning" (dvs lite sträng) om I till varje nod så att: (1) den maximala storleken på råden är som mest m bitar, och (2) problemet P kan lösas distributivt i de flesta t rundor med hjälp av råden som ingångar. När det gäller MST, den utdata som returneras av varje nod av en viktad graf G är kanten som leder till dess förälder i några rotade MST T av G. Uppenbarligen finns det en trivial ( log n, 0)-anvisningsschema för MST (varje nod ges det lokala portnumret av kanten som leder till roten av vissa MST T ), och det är känt att alla (0, t)-anvisningsschema uppfyller t ≥  på ( ș n). Vårt huvudsakliga resultat är byggandet av ett (O(1), O(log n))-anvisningssystem för MST. Det vill säga, genom att bara ge ett konstant antal bitar av råd till varje nod, kan man minska exponentiellt den distribuerade beräkningstiden för MST i godtycklig graf, jämfört med algoritmer som behandlar problemet i avsaknad av en priori information. Vi tar också hänsyn till den genomsnittliga storleken på råden. Å ena sidan visar vi att alla (m, 0)-anvisningsprogram för MST ger råd av genomsnittlig storlek (log n). Å andra sidan utformar vi ett (m, 1)-vägledande schema för MST med råd av konstant genomsnittlig storlek, det är en runda är tillräckligt för att minska den genomsnittliga storleken på råden från log n till konstant. Teorisammanställning Syst (2010) 47: 920-933 921
I REF visades att råd av konstant storlek som ges till noderna möjliggör distribuerad konstruktion av ett minsta spännträd i logaritmisk tid.
Local MST Computation with Short Advice
{'venue': 'Theory of Computing Systems', 'journal': 'Theory of Computing Systems', 'mag_field_of_study': ['Mathematics', 'Computer Science']}