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
 
Contributor
 
Date 1987-03-01
 
Type info:eu-repo/semantics/article
info:eu-repo/semantics/publishedVersion
Peer-reviewed Article
 
Format application/pdf
 
Identifier http://ojs.statsbiblioteket.dk/index.php/daimipb/article/view/7575
10.7146/dpb.v16i226.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
2245-9316
0105-8517
 
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

Twitter

Copyright © 2015-2018 Simon Fraser University Library