Robert G. Farrell, Catalina M. Danis, et al.
RecSys 2012
We consider the problem of constructing a rooted spanning tree in an anonymous connected) network. In case no upper bound on the network size is known, we give the following algorithms, all of which have error probability ε: (1) A message terminating algorithm that runs in O(n) time and O(m log(n2/m)) messages, each of size O(log(n/ε)), where n and m are the number of nodes and links in the network. (2) A message terminating algorithm with expected running time O(n log log(n/ε)) and expected message complexity O(n log n + m log log(n/ε)), each of size O(log(n/ε)). For any fixed ε, this algorithm can be modified to run in O(nf(n)) expected time and O(n log n + mf(n)) expected message complexity, where f(n) is any slowly-growing function. However, this requires the use of longer messages. In case an upper bound on the network size is known, we give a processor terminating algorithm with error probability ε that runs in O(n) time, and O(n log n + m) messages. Finally, in case the network size is known within a factor of 2, we give an algorithm that processor terminates and always succeeds, in expected O(n) time and O(n log n + m) messages. © 1994 Academic Press, Inc.
Robert G. Farrell, Catalina M. Danis, et al.
RecSys 2012
Elizabeth A. Sholler, Frederick M. Meyer, et al.
SPIE AeroSense 1997
Apostol Natsev, Alexander Haubold, et al.
MMSP 2007
David A. Selby
IBM J. Res. Dev