Study of General Incomplete Star Interconnection Networks

The star networks, which were originally proposed by Akers and Harel,have suffered from a rigorous restriction on the number of nodes. Thegeneral incomplete star networks (GISN) are proposed in thispaper to relieve this restriction. Anefficient labeling scheme for GISN is given, and routing andbroadcasting algorithms are also presented for GISN. Thecommunication diameter of GISN is shown to be bounded by4n-7. The proposed single node broadcasting algorithm isoptimal with respect to time complexity O(n\log_2 n).