Incomplete star graph: an alternative interconnection network for massively parallel systems

The authors introduce a new interconnection network for massively parallel systems called the incomplete star graph. They describe unique ways of interconnecting and labeling the nodes, and routing point-to-point communications within this network. A special class of the incomplete star graph is presented and the network measures for this special class are derived. An n-dimensional star graph increases by a factor of (n+1)>2 every time it grows to the next dimension. One of the main contributions is the development of a selection method for designing an m-processor network with (n-1)-factorial<m<n-factorial out of n-factorial possible permutations