Construction of redundant networks with minimum distance

✍ Scribed by M.R. Steffen; Warren Dent

• Publisher: Elsevier Science
• Year: 1970
• Tongue: English
• Weight: 583 KB
• Volume: 289
• Category: Article
• ISSN: 0016-0032
• DOI: 10.1016/0016-0032(70)90287-5

✦ Synopsis

A method for constructing redundant network8 and simultaneously minimizing total distance is presented. The method is well suited for digital computation.

Its application to message switching systems is briefly discussed.

1. Zntroduction

A communication network in which each station is connected to its nearest neighbors is called a distributed network by Baran (1). The number of nearest neighbors of a vertex (station) is called its redundancy. Baran shows that a distributed network with local switching capability to the non-busy redundant stations results in an adaptive network with high reliability and message-handling capability.

It is not obvious how such a network can be constructed for a specified redundancy under the requirement that the network be connected. As an example, Fig. illustrates that connecting each of the six points to its two nearest neighbors does not result in a connected network.

DeJinition. A network of n vertices is called Ic redundant if each of its vertices is connected to at least its k nearest neighbors, where 1~ Ic < n -1.

ZZ.