Browse Prior Art Database

# Distributed Minimal Spanning Tree Algorithm

IP.com Disclosure Number: IPCOM000107199D
Original Publication Date: 1992-Jan-01
Included in the Prior Art Database: 2005-Mar-21
Document File: 7 page(s) / 274K

IBM

## Related People

Boyles, RW: AUTHOR [+1]

## Abstract

Disclosed is an efficient algorithm that builds a minimal spanning tree of a network or sub-network, with a significant reduction in computational complexity. At each individual node, the computational complexity of this distributed minimal spanning tree algorithm can be generalized as (Average_node_degree)x(Log N). For comparison, the corresponding computational complexity of a non-distributed minimal spanning tree algorithm would be (N)x(Average_node_degree)x(Log N). Note that there is an N-fold improvement (N is the number of nodes in the tree).

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 19% of the total text.

Distributed Minimal Spanning Tree Algorithm

Disclosed is an efficient algorithm that builds a minimal
spanning tree of a network or sub-network, with a significant
reduction in computational complexity.  At each individual node, the
computational complexity of this distributed minimal spanning tree
algorithm can be generalized as (Average_node_degree)x(Log N).  For
comparison, the corresponding computational complexity of a
non-distributed minimal spanning tree algorithm would be
(N)x(Average_node_degree)x(Log N).  Note that there is an N-fold
improvement (N is the number of nodes in the tree).

In many networks, it is often desirable to establish a minimal
spanning tree (MST) containing all the nodes of a network, or a
subset of those nodes.  In this algorithm, the minimal spanning tree
is formed by selecting the links between the nodes in a network or
sub-network so as to minimize the total weight of all links
comprising the minimal spanning tree.  (The term "links" is used here
in a generic sense.  If the MST connects all nodes in the network, a
the two nodes.  If the MST connects a subset of nodes, a "link"
between two MST nodes is the shortest path connecting the two nodes.
The shortest path is the path, among all the paths connecting the two
nodes, with minimal total link weight.  (A path may consist of one or
Therefore, a minimal spanning tree will represent the most efficient
connection of a number of nodes for a particular link weight scheme.

With conventional methods, there are two general approaches for
the MST calculation.  One is to determine the MST at each node.  The
other is to determine the MST at one or a few centralized nodes and
then broadcast the MST data to the other nodes comprising the MST.
In either case, at each of the nodes doing the MST calculation, the
computational complexity for determining the minimal spanning tree of
N nodes is:  O(N)x(d_ave)x(Log N)) where d_ave is the average node
degree (the average number of links connecting to a node), and O is
an annotation indicating order of complexity.