Design to Minimize Diameter on Building-Block Network

1 June 1981

journal article
Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers

Vol. C-30 (6) , 439-442
https://doi.org/10.1109/tc.1981.1675809

Abstract

This paper proposes a simple algorithm for the graph design of small-diameter networks. For given nodes n and degree d, this algorithm can be used to construct a directed graph with diameter ⌈logd n⌉, which is at most one larger than the lower bound ⌈logd (n(d − 1) + 1)⌉ − 1. Its average distance is also close to the lower bound. The algorithm can be used to construct a directed graph with smaller diameter, compared with any other conventional methods, when n is larger.

Keywords

This publication has 6 references indexed in Scilit:

The Design of Small-Diameter Networks by Local Search
IEEE Transactions on Computers, 1979
A Combinatorial Problem Related to Multimodule Memory Organizations
Journal of the ACM, 1974
On (d, k) Graphs
IEEE Transactions on Electronic Computers, 1967
A Design for (d, k) Graphs
IEEE Transactions on Electronic Computers, 1966
On the Construction of (d, k) Graphs
IEEE Transactions on Electronic Computers, 1965
Topological constraints on interconnection-limited logic
Published by Institute of Electrical and Electronics Engineers (IEEE) ,1964