A class of fixed-degree Cayley-graph interconnection networks derived by pruning k-ary n-cubes

Author

Kwai, Ding-Ming ; Parhami, Behrooz

Author_Institution

Dept. of Electr. & Comput. Eng., California Univ., Santa Barbara, CA, USA

fYear

1997

fDate

11-15 Aug 1997

Firstpage

92

Lastpage

95

Abstract

We introduce a pruning scheme to reduce the node degree of k-ary n-cube from 2n to 4. The links corresponding to n-2 of the n dimensions are removed from each node. One of the remaining dimensions is common to all nodes and the other is selected periodically from the remaining n-1 dimensions. Despite the removal of a large number of links from the k-ary n-cube, this incomplete version still preserves many of its desirable topological properties. In this paper, we show that this incomplete k-ary n-cube belongs to the class of Cayley graphs, and hence, is node-symmetric. It is 4-connected with diameter close to that of the k-ary n-cube

Keywords

graph theory; multiprocessor interconnection networks; Cayley graphs; fixed-degree Cayley-graph interconnection networks; k-ary n-cubes; pruning scheme; topological properties; Hypercubes; Multiprocessor interconnection networks; Partial response channels; Very large scale integration;

fLanguage

English

Publisher

ieee

Conference_Titel

Parallel Processing, 1997., Proceedings of the 1997 International Conference on

Conference_Location

Bloomington, IL

ISSN

0190-3918

Print_ISBN

0-8186-8108-X

Type

conf

DOI

10.1109/ICPP.1997.622563

Filename

622563