On generalized diameters of interconnection networks

摘要

The authors study the generalized diameters for many existing networks for parallel computations, such as trees, hypercubes, meshes and butterflies. The generalized diameter, called the i-ameter and denoted by d/sub i/(G), of a graph G=(V,E) is the length of the shortest Steiner tree that can be established between any i nodes in G. This generalized notion of diameter allows the computation of the communication cost for any number of nodes, in a given network. Exact values of the i-ameter are computed for complete binary trees and the k-ary trees. For other networks, exact values of i-ameter are given for smaller values of i, and bounds are given for higher values.