## Abstract

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(n^{2}/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.

Original language | English (US) |
---|---|

Pages (from-to) | 80-101 |

Number of pages | 22 |

Journal | Information and Computation |

Volume | 113 |

Issue number | 1 |

DOIs | |

State | Published - Aug 15 1994 |

Externally published | Yes |

## ASJC Scopus subject areas

- Theoretical Computer Science
- Information Systems
- Computer Science Applications
- Computational Theory and Mathematics