Embedding Star Networks into Hypercubes
| dc.contributor.author | Bettayeb, Said | |
| dc.date.accessioned | 2020-05-04T16:05:15Z | |
| dc.date.available | 2020-05-04T16:05:15Z | |
| dc.date.issued | 1996 | |
| dc.description.abstract | The star interconnection network has recently been suggested as an alternative to the hypercube. As hypercubes are often viewed as universal and capable of simulating other architectures efficiently, we investigate embeddings of star network into hypercubes. Our embeddings exhibit a marked trade off between dilation and expansion. For the n dimensional star network we exhibit: (1) a dilation N-1 embedding of S/sub n/ into H/sub n/, where N=[log/sub 2/(n!)]; (2) a dilation 2(d+1) embedding of S/sub n/ into H/sub 2d+n-1/ where d=[log/sub 2/([n/2]!)]; (3) a dilation 2d+2i embedding of S(2/sup i/m) into H(2/sup i/d+i2/sup i/m-2i+1) where d=[log/sub 2/(m!)]; (4) a dilation L embedding of S/sub n/ into H/sub d/, where L=1+[log/sub 2/(n!)], and d=(n-1)L; (5) a dilation (k+1)(k+2)/2 embedding of S/sub n/ into H(n(k+1)-2/sup k+1/+1) where k=[log/sub 2/(n-1)]; (6) a dilation 3 embedding of S/sub 2k+1/ into H(2k/sup 2/+k); and (7) a dilation 4 embedding of S/sub 3k+2/ into H(3k/sup 2/+3k+1). Some of the embeddings are in fact optimum, in both dilation and expansion for small values of n. We also show that the embedding of S/sub n/ into its optimum hypercube requires dilation /spl Omega/(log/sub 2/ n). | en_US |
| dc.identifier.citation | • Embedding Star Networks into Hypercubes, (with B. Cong, M. Girou , and I.H. Sudborough), IEEE Trans. on Computers, Vol.45 No. 2, Feb.1996, pp.186-194. | en_US |
| dc.identifier.uri | https://hdl.handle.net/10657.1/2323 | |
| dc.publisher | IEEE Transactions on Computers | en_US |
| dc.subject | Hypercubes, Computer science, Genetic mutations, Multiprocessor interconnection networks, Computer networks, Concurrent computing | en_US |
| dc.title | Embedding Star Networks into Hypercubes | en_US |
| dc.type | Article | en_US |
Files
Original bundle
1 - 1 of 1
Loading...
- Name:
- Embedding Star Networks into Hypercubes.pdf
- Size:
- 8.24 KB
- Format:
- Adobe Portable Document Format
- Description:
License bundle
1 - 1 of 1
No Thumbnail Available
- Name:
- license.txt
- Size:
- 1.71 KB
- Format:
- Item-specific license agreed upon to submission
- Description: