Title: | Routing properties of supercubes |
Authors: | Sheu, JJ Tan, JJ Hsu, LH 資訊工程學系 Department of Computer Science |
Keywords: | interconnection networks;hypercube;supercube;container;wide diameter;fault diameter |
Issue Date: | 1-Jan-2001 |
Abstract: | Usually each vertex of the (s + 1)-dimensional hypercube is labeled with a unique integer k with 0 less than or equal to k less than or equal to 2(s+1) - 1. The supercube S-N of N nodes with 2(s) < N <less than or equal to> 2(s+1) is constructed by merging nodes u and u - 2(s), with N less than or equal to u less than or equal to 2(s+1) - 1, in the (s + 1)-dimensional hypercube into a single node labeled as u - 2(s) and leaving other nodes in the (s + I)-dimensional hypercube unchanged. In this paper, we give the exact distance between any two nodes of supercube and present a new shortest path routing algorithm on S-N Then we show how to construct kappa (S-N) disjoint paths between any two nodes of the supercube, where kappa (S-N) is the connectivity of S-N. Finally, we compute the wide diameter and the fault diameter of SN We show that both the wide diameter and the fault diameter are equal to s + 2 if N is an element of (2(s+1) - 2(i) + 1 0 less than or equal to i less than or equal to s - 1) and s + 1 otherwise. (C) 2001 Elsevier Science Inc. All rights reserved. |
URI: | http://dx.doi.org/10.1016/S0020-0255(00)00089-X http://hdl.handle.net/11536/30041 |
ISSN: | 0020-0255 |
DOI: | 10.1016/S0020-0255(00)00089-X |
Journal: | INFORMATION SCIENCES |
Volume: | 131 |
Issue: | 1-4 |
Begin Page: | 107 |
End Page: | 128 |
Appears in Collections: | Articles |
Files in This Item:
If it is a zip file, please download the file and unzip it, then open index.html in a browser to view the full text content.