A complete spanning tree maintenance algorithm and its complexity
Akinori Saitoh, Yoshihiro Tsujino, Nobuki Tokura · Systems and Computers in Japan · 1992
Abstract The spanning tree maintenance problem for an LAN model in which node processors may halt and recover is considered. An algorithm meeting the conditions that the spanning tree is an L‐ary complete tree and that nodes halt or recover singly is presented. The message complexity of this algorithm is shown to be comparable with local computational complexity.