Title :
A linear-time algorithm for computing the diameters of the incomplete WK-recursive networks
Author :
Su, Min-Yang ; Chen, Gen-Huey ; Duh, Dyi-Rong
Author_Institution :
Dept. of Comput. Sci. & Inf. Eng., Nat. Taiwan Univ., Taipei, Taiwan
Abstract :
The WK-recursive networks, which were originally proposed by Vecchia and Sanges, have suffered from the rigorous restriction on the number of nodes. Like the other incomplete networks, the incomplete WK-recursive networks have been proposed to relieve this restriction. In this paper, it is first shown that the structures of the incomplete WK-recursive networks are conveniently represented with multistage graphs. This representation can provide a uniform look at the incomplete WK-recursive networks. With its help, a linear-time algorithm using the prune-and-search technique is presented for computing the diameters of the incomplete WK-recursive networks
Keywords :
multistage interconnection networks; WK-recursive networks; interconnection network; linear-time algorithm; multiprocessor system; multistage graphs; prune-and-search technique; Algorithm design and analysis; Computer networks; Computer science; Costs; Educational institutions; Manufacturing; Multiprocessing systems; Multiprocessor interconnection networks; Network topology; Scalability;
Conference_Titel :
Parallel and Distributed Systems, 1996. Proceedings., 1996 International Conference on
Conference_Location :
Tokyo
Print_ISBN :
0-8186-7267-6
DOI :
10.1109/ICPADS.1996.517549
