Title :
Design to Minimize Diameter on Building-Block Network
Author :
Imase, Makoto ; Itoh, Masaki
Author_Institution :
Musashino Electrical Communication Laboratory, Nippon Telegraph and Telephone Public Corporation
fDate :
6/1/1981 12:00:00 AM
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 :
Building-block; diameter minimization; distance; lower bounds; nearly optimum solution; switching system; undirected graph; Algorithm design and analysis; Communication switching; Large scale integration; Length measurement; Switching systems; Telegraphy; Telephony; Tree graphs; Building-block; diameter minimization; distance; lower bounds; nearly optimum solution; switching system; undirected graph;
Journal_Title :
Computers, IEEE Transactions on
DOI :
10.1109/TC.1981.1675809
