A Distributed Spanning Tree Algorithm

DAIMI Report Series

View Publication Info
Field Value
Title A Distributed Spanning Tree Algorithm
Creator Johansen, Karl Erik
Jørgensen, Ulla Lundin
Nielsen, Sven Hauge
Nielsen, Søren Erik
Skyum, Sven
Description 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.
Publisher Aarhus University
Date 1987-03-01
Type info:eu-repo/semantics/article
Peer-reviewed Article
Format application/pdf
Identifier http://ojs.statsbiblioteket.dk/index.php/daimipb/article/view/7575
Source DAIMI Report Series; No 226 (1987): PB-226 A Distributed Spanning Tree Algorithm
DAIMI Report Series; No 226 (1987): PB-226 A Distributed Spanning Tree Algorithm
Language eng
Relation http://ojs.statsbiblioteket.dk/index.php/daimipb/article/view/7575/6422

Contact Us

The PKP Index is an initiative of the Public Knowledge Project.

For PKP Publishing Services please use the PKP|PS contact form.

For support with PKP software we encourage users to consult our wiki for documentation and search our support forums.

For any other correspondence feel free to contact us using the PKP contact form.

Find Us


Copyright © 2015-2018 Simon Fraser University Library