Embedding between Hypercube and HCN(n, n), HFN(n, n)


The KIPS Transactions:PartA, Vol. 9, No. 2, pp. 191-196, Jun. 2002
10.3745/KIPSTA.2002.9.2.191,   PDF Download:

Abstract

It is one of the important measures in the area of algorithm design that any interconnection network should be embedded into another interconnection network for the practical use of algorithm. A HCN(n, n), HFN(n, n) graph also has such a good properties of a hypercube and has a lower network cost than a hypercube. In this paper, we propose a method to embed between hypercube Q2n and HCN(n, n), HFN(n, n) graph. We show that hypercube Q2n can be embedded into an HCN(n, n) and HFN(n, n) with dilation 3, and average dilation is smaller than 2. Also, we has a result that the embedding cost, a HCN(n, n) and HFN(n, n) can be embedded into a hypercube, is O (n).


Statistics
Show / Hide Statistics

Statistics (Cumulative Counts from September 1st, 2017)
Multiple requests among the same browser session are counted as one view.
If you mouse over a chart, the values of data points will be shown.


Cite this article
[IEEE Style]
J. S. Kim, H. O. Lee, Y. N. Heo, "Embedding between Hypercube and HCN(n, n), HFN(n, n)," The KIPS Transactions:PartA, vol. 9, no. 2, pp. 191-196, 2002. DOI: 10.3745/KIPSTA.2002.9.2.191.

[ACM Style]
Jong Seok Kim, Hyeong Ok Lee, and Yeong Nam Heo. 2002. Embedding between Hypercube and HCN(n, n), HFN(n, n). The KIPS Transactions:PartA, 9, 2, (2002), 191-196. DOI: 10.3745/KIPSTA.2002.9.2.191.