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

fYear

1996

fDate

3-6 Jun 1996

Firstpage

90

Lastpage

97

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;

fLanguage

English

Publisher

ieee

Conference_Titel

Parallel and Distributed Systems, 1996. Proceedings., 1996 International Conference on

Conference_Location

Tokyo

Print_ISBN

0-8186-7267-6

Type

conf

DOI

10.1109/ICPADS.1996.517549

Filename

517549