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:

  1. 000168088100006.pdf

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.