A distributed spanning tree algorithm

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

doi:10.1007/BFb0019790

A distributed spanning tree algorithm

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

Publikation: Bidrag til bog/antologi/rapport/proceeding › Konferencebidrag i proceedings › Forskning › peer review

5 Citationer (Scopus)

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 asyncronous. 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.

Originalsprog	Engelsk
Titel	Distributed Algorithms : 2nd International Workshop Amsterdam, The Netherlands, July 8–10, 1987 Proceedings
Redaktører	Jan van Leeuwen
Antal sider	12
Forlag	Springer
Publikationsdato	1988
Sider	1-12
DOI	https://doi.org/10.1007/BFb0019790
Status	Udgivet - 1988
Begivenhed	2nd International Workshop on Distributed Algorithms - Amsterdam, Holland Varighed: 8 jul. 1987 → 10 jul. 1987

Konference

Konference	2nd International Workshop on Distributed Algorithms
Land/Område	Holland
By	Amsterdam
Periode	08/07/1987 → 10/07/1987

Navn	Lecture Notes in Computer Science
Vol/bind	312

Adgang til dokumentet

10.1007/BFb0019790

Citationsformater

@inproceedings{26a6a2abff4840458f5d170f3d75d0a3,

title = "A distributed spanning tree algorithm",

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 asyncronous. 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 = "Johansen, {Karl Erik} and J{\o}rgensen, {Ulla Lundin} and Nielsen, {Svend Hauge} and Nielsen, {S{\o}ren Erik} and Sven Skyum",

year = "1988",

doi = "10.1007/BFb0019790",

language = "English",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "1--12",

editor = "{van Leeuwen}, Jan",

booktitle = "Distributed Algorithms",

address = "Netherlands",

note = "2nd International Workshop on Distributed Algorithms ; Conference date: 08-07-1987 Through 10-07-1987",

}

Johansen, KE, Jørgensen, UL, Nielsen, SH, Nielsen, SE & Skyum, S 1988, A distributed spanning tree algorithm. i J van Leeuwen (red.), Distributed Algorithms: 2nd International Workshop Amsterdam, The Netherlands, July 8–10, 1987 Proceedings. Springer, Lecture Notes in Computer Science, bind 312, s. 1-12, 2nd International Workshop on Distributed Algorithms, Amsterdam, Holland, 08/07/1987. https://doi.org/10.1007/BFb0019790

A distributed spanning tree algorithm. / Johansen, Karl Erik; Jørgensen, Ulla Lundin; Nielsen, Svend Hauge et al.
Distributed Algorithms: 2nd International Workshop Amsterdam, The Netherlands, July 8–10, 1987 Proceedings. red. / Jan van Leeuwen. Springer, 1988. s. 1-12 (Lecture Notes in Computer Science, Bind 312).

Publikation: Bidrag til bog/antologi/rapport/proceeding › Konferencebidrag i proceedings › Forskning › peer review

TY - GEN

T1 - A distributed spanning tree algorithm

AU - Johansen, Karl Erik

AU - Jørgensen, Ulla Lundin

AU - Nielsen, Svend Hauge

AU - Nielsen, Søren Erik

AU - Skyum, Sven

PY - 1988

Y1 - 1988

N2 - 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 asyncronous. 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.

AB - 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 asyncronous. 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.

U2 - 10.1007/BFb0019790

DO - 10.1007/BFb0019790

M3 - Article in proceedings

T3 - Lecture Notes in Computer Science

SP - 1

EP - 12

BT - Distributed Algorithms

A2 - van Leeuwen, Jan

PB - Springer

T2 - 2nd International Workshop on Distributed Algorithms

Y2 - 8 July 1987 through 10 July 1987

ER -

A distributed spanning tree algorithm

Abstract

Konference

Adgang til dokumentet

Fingeraftryk

Citationsformater