The Cost of Broadcasting on Star Graphs and k-ary Hypercubes

It is shown that, for two common broadcasting problems, a star graph performs better than a k-ary hypercube with a comparable number of nodes only in networks consisting of impractically large numbers of nodes. This result is based on a comparison of the costs of known solutions to the one-to-all broadcast and the complete broadcast problems for each network. The cost of solutions to these common problems is a better indication of the expected performance of an interconnection network than is a comparison of scalar measures such as the diameter and degree. © 1993 IEE