Exact Solutions to Diameter and Routing Problems in PEC Networks

✍ Scribed by C.S. Raghavendra; M.A. Sridhar

• Publisher: Elsevier Science
• Year: 1996
• Tongue: English
• Weight: 339 KB
• Volume: 34
• Category: Article
• ISSN: 0743-7315
• DOI: 10.1006/jpdc.1996.0056

✦ Synopsis

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 an N ‫؍‬ 2 n node PEC network, with ͙2n an integer, it is shown that the diameter is given by the simple expression 2 (͙2n؊3) (3͙2n ؊ 2). An exact expression for the diameter of PEC networks for general N is also derived. Efficient algorithms for shortest-path routing between 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 between nodes. Finally, a simple modification to obtain symmetric PEC networks is suggested.