Embedding between a Macro-Star Graph and a Matrix Star Graph


The Transactions of the Korea Information Processing Society (1994 ~ 2000), Vol. 6, No. 3, pp. 571-579, Mar. 1999
10.3745/KIPSTE.1999.6.3.571,   PDF Download:

Abstract

A Macro-Star graph which has a star graph as a basic module has node symmetry, maximum fault tolerance, and hierarchical decomposition property. And, it is an interconnection network which improves a network cost against a star graph. a matrix star graph also has such good properties of a Macro-Star graph and is an interconnection network which has a lower network cost than a Macro-Star graph. In this paper, we propose a method to embed between a Macro-Star graph and a matrix star graph. We show that a Macro-Star graph MS(k,n) can be embedded into a matrix star graph MSk,n 1 with dilation 2. In addition, we show that a matrix star graph MSk,n can be embedded into a Macro-Star graph MS(k,n 1) with dilation 4 and average dilation 3 or less as well. This result means that several algorithms developed in a star graph can be simulated in a matrix star graph with constant cost.


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]
L. H. Ok, "Embedding between a Macro-Star Graph and a Matrix Star Graph," The Transactions of the Korea Information Processing Society (1994 ~ 2000), vol. 6, no. 3, pp. 571-579, 1999. DOI: 10.3745/KIPSTE.1999.6.3.571.

[ACM Style]
Lee Hyeong Ok. 1999. Embedding between a Macro-Star Graph and a Matrix Star Graph. The Transactions of the Korea Information Processing Society (1994 ~ 2000), 6, 3, (1999), 571-579. DOI: 10.3745/KIPSTE.1999.6.3.571.