A Distributed Spanning Tree Algorithm

Authors

  • Karl Erik Johansen
  • Ulla Lundin Jørgensen
  • Sven Hauge Nielsen
  • Søren Erik Nielsen
  • Sven Skyum

DOI:

https://doi.org/10.7146/dpb.v16i226.7575

Abstract

We present a distributed algorithm for constructing a spanning tree for connected undirected graphs. Nodes correspond to processors and edges correspond to two-way channels. Each processor has initially a distinct identity and all processors perform the same algorithm. Computation as well as communication is asynchronous. The total number of messages sent during a construction of a spanning tree is at most 2E+3NlogN. The maximal message size is loglogN+log(maxid)+3, where maxid is the maximal processor identity.

Author Biographies

Karl Erik Johansen

Ulla Lundin Jørgensen

Sven Hauge Nielsen

Søren Erik Nielsen

Sven Skyum

Downloads

Published

1987-03-01

How to Cite

Johansen, K. E., Jørgensen, U. L., Nielsen, S. H., Nielsen, S. E., & Skyum, S. (1987). A Distributed Spanning Tree Algorithm. DAIMI Report Series, 16(226). https://doi.org/10.7146/dpb.v16i226.7575

Issue

No. 226 (1987): PB-226 A Distributed Spanning Tree Algorithm

Section

Articles

License

Creative Commons License

Articles published in DAIMI PB are licensed under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.