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. Symposium on Parallel and Distributed Processing, 1992, pp. 368–375], who presented asymptotically tight bounds for the diameter and showed asymptotically optimal routing algorithms. In this paper exact, solutions to the diameter and routing problems of PEC networks are derived, thereby strengthening the asymptotic bounds of Lin and Prasanna. For anN= 2ⁿnode PEC network, withformula]an integer, it is shown that the diameter is given by the simple expressionformula]An exact expression for the diameter of PEC networks for generalNis also derived. Efficient algorithms for shortest-path routing between nodes in a PEC network are then developed. These algorithms use at mostO(log²N) time for computing the lengths of minimal routes between nodes. Finally, a simple modification to obtain symmetric PEC networks is suggested.