A Distributed Spanning Tree Algorithm

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

A Distributed Spanning Tree Algorithm

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

Research output: Book/anthology/dissertation/report › Report › Research

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.

Original language	English

Publisher	Department of Computer Science, Aarhus University
Number of pages	13
Publication status	Published - 1987

Series	DAIMI PB
Number	226

Cite this

@book{e266d62448a242fd94ec77ed5e8681ee,

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

year = "1987",

language = "English",

series = "DAIMI PB",

number = "226",

publisher = "Department of Computer Science, Aarhus University",

}

TY - RPRT

T1 - A Distributed Spanning Tree Algorithm

AU - Johansen, Karl Erik

AU - Jørgensen, Ulla Lundin

AU - Nielsen, Sven Hauge

AU - Nielsen, Søren Erik

AU - Skyum, Sven

PY - 1987

Y1 - 1987

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

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

M3 - Report

T3 - DAIMI PB

BT - A Distributed Spanning Tree Algorithm

PB - Department of Computer Science, Aarhus University

ER -

A Distributed Spanning Tree Algorithm

Abstract

Fingerprint

Cite this