EXACT-SOLUTIONS TO DIAMETER AND ROUTING-PROBLEMS IN PEC NETWORKS

Recently, the diameter problem for packed exponential connections (PEC ) networks was addressed by Cho-Chin Lin and V. K. Prasanna [Proc. Sym posium on Parallel and Distributed Processing, 1992, pp, 368-375], who presented asymptotically tight bounds for the diameter and showed asy mptotically optimal routing algorithms, In this paper exact, solutions to the diameter and routing problems of PEC networks are derived, the reby strengthening the asymptotic bounds of Lin and Prasanna, For an N = 2 '' node PEC network, with root 2n an integer, it is shown that th e diameter is given by the simple expression 2((root 2n-3)) (3 root 2n -2). An exact expression for the diameter of PEC networks for general N is also derived, Efficient algorithms for shortest-path routing betw een nodes in a PEC network are then developed, These algorithms use at most O(log(2) N) time for computing the lengths of minimal routes bet ween nodes, Finally, a simple modification to obtain symmetric PEC net works is suggested. (C) 1996 Academic Press, Inc.