DocumentCode
1144299
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
Issue
6
fYear
1981
fDate
6/1/1981 12:00:00 AM
Firstpage
439
Lastpage
442
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;
fLanguage
English
Journal_Title
Computers, IEEE Transactions on
Publisher
ieee
ISSN
0018-9340
Type
jour
DOI
10.1109/TC.1981.1675809
Filename
1675809
Link To Document