Abstrakt. Med tanke på en 2-node ansluten, oriktad graf G = (V, E), med n noder och m kanter med verkliga vikter, och med tanke på en minsta spännvidd träd (MST) T = (V, ET ) av G, studerar vi problemet med att hitta, för varje nod v  och V, MST där Ev är uppsättningen av kanter incident till v i G. Vi visar att detta problem kan lösas i O(min(m · α(n, n), m + n log n) tid och O(m) utrymme. Vår lösning förbättrar den tidigare kända tiden för O(m log n).
I själva verket togs denna logaritmiska faktor bort i REF, där författarna utarbetade en O(min {m · α(n, n), m + n log n}) tid och linjär rymdalgoritm.
Maintaining a Minimum Spanning Tree under Transient Node Failures
{'venue': 'ICALP', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}