Study of General Incomplete Star Interconnection Networks

The star networks, which were originally proposed by Akers and Harel, havesuffered from a rigorous restriction on the number of nodes. The general incomplete starnetworks (GISN) are proposed in this paper to relieve this restriction. An efficient labelingscheme for GISN is given, and routing and broadcasting a1gorithms are also presented forGlSN. The communication diameter of GISN is shown to be bounded by 4n - 7. The proposedsingle node broadcasting algorithm is optimal with respect to time complexity O(nlog2,n).