文章基本信息

标题：Routing and Broadcasting Algorithms for Generalized-Star Cube
本地全文：下载
作者：Daiki Arai ; Yamin Li
期刊名称：International Journal of Networking and Computing
印刷版ISSN：2185-2847
出版年度：2016
卷号：6
期号：2
页码：368-394
语种：English
出版社：International Journal of Networking and Computing
摘要：In this paper, another version of the star cube called the generalized-star cube, GSC(n,k,m), is presented as a three level interconnection topology. GSC(n,k,m) is a product graph of the (n,k)-star graph and the m-dimensional hypercube (m-cube). It can be constructed in one of two ways: to replace each node in an m-cube with an (n,k)-star graph, or to replace each node in an (n,k)-star graph with an m-cube. Because there are three parameters m, n, and k, the network size of GSC(n,k,m) can be changed more flexibly than the star graph, star-cube, and (n,k)-star graph. We first investigate the topological properties of the GSC(n,k,m), such as the node degree, diameter, average distance, and cost. Also, the regularity and node symmetry of the GSC(n,k,m) are derived. Next, we present a formal shortest-path routing algorithm. Then, we give broadcasting algorithms for both of the single-port and all-port models. To develop these algorithms, we use the spanning binomial tree, the neighborhood broadcasting algorithm, and the minimum dominating set. The complexities of the routing and broadcasting algorithms are also examined.
其他摘要：In this paper, another version of the star cube called the generalized-star cube, GSC(n,k,m), is presented as a three level interconnection topology. GSC(n,k,m) is a product graph of the (n,k)-star graph and the m-dimensional hypercube (m-cube). It can be constructed in one of two ways: to replace each node in an m-cube with an (n,k)-star graph, or to replace each node in an (n,k)-star graph with an m-cube. Because there are three parameters m, n, and k, the network size of GSC(n,k,m) can be changed more flexibly than the star graph, star-cube, and (n,k)-star graph. We first investigate the topological properties of the GSC(n,k,m), such as the node degree, diameter, average distance, and cost. Also, the regularity and node symmetry of the GSC(n,k,m) are derived. Next, we present a formal shortest-path routing algorithm. Then, we give broadcasting algorithms for both of the single-port and all-port models. To develop these algorithms, we use the spanning binomial tree, the neighborhood broadcasting algorithm, and the minimum dominating set. The complexities of the routing and broadcasting algorithms are also examined.