Skip to main content

Maximal Chained Networks of Given Diameter with transputer examples

Brian R. Stonebridge, Maximal Chained Networks of Given Diameter with transputer examples. CSTR-95-004, Department of Computer Science, University of Bristol. March 1995. PDF, 138 Kbytes.


The property that a network is chained (possesses a Hamiltonian path) is important in some practical transputer applications. It is also desirable that, for a given order of network (number of nodes), the diameter should be as small as possible to facilitate cross-network communication; conversely, for a given diameter, there is a maximum possible configuration. We therefore seek the configuration of a network with prescribed diameter and of maximum order. We show that by a suitable representation of such a network, the natural constraints lead to a useful bound for the order of the network and a simple configuration which provides a lower bound for the diameter of the maximal network. The diameters of Hamiltonian nets are deduced from the lowest power of the adjacency matrix which gives its transitive closure. The special structure of the adjacency matrix for Hamiltonian systems allows an efficient covering which is then tuned to satisfy practical constraints. The diameters of the configurations are readily evaluated.

Bibtex entry.

Publication Admin