? 交换交叉立方体中最优路径的嵌入
Journal of Computer Science and Technology
Quick Search in JCST
 Advanced Search 
      Home | PrePrint | SiteMap | Contact Us | Help
 
Indexed by   SCIE, EI ...
Bimonthly    Since 1986
Journal of Computer Science and Technology 2017, Vol. 32 Issue (3) :618-629    DOI: 10.1007/s11390-017-1729-8
Theory and Algorithms << Previous Articles | Next Articles >>
交换交叉立方体中最优路径的嵌入
Dong-Fang Zhou1, Jian-Xi Fan1,2,*, Member, CCF, Cheng-Kuan Lin1, Member, CCF, Bao-Lei Cheng1, Member, CCF, Jing-Ya Zhou1, Member, CCF, Zhao Liu1
1. School of Computer Science and Technology, Soochow University, Suzhou 215006, China;
2. Collaborative Innovation Center of Novel Software Technology and Industrialization, Nanjing University Nanjing 210000, China
Optimal Path Embedding in the Exchanged Crossed Cube
Dong-Fang Zhou1, Jian-Xi Fan1,2,*, Member, CCF, Cheng-Kuan Lin1, Member, CCF, Bao-Lei Cheng1, Member, CCF, Jing-Ya Zhou1, Member, CCF, Zhao Liu1
1. School of Computer Science and Technology, Soochow University, Suzhou 215006, China;
2. Collaborative Innovation Center of Novel Software Technology and Industrialization, Nanjing University Nanjing 210000, China

摘要
参考文献
相关文章
Download: [PDF 443KB]  
摘要 s+t+1维的交换交叉立方体网络可以表示为,它保持了交换超立方网络与交叉立方体网络的许多优点。例如:研究者已经证明比常见的超立方网络的变型在边数、硬件成本开销、直径方面具有较优越的性质。在本文中,我们研究了网络中任意两个不同顶点之间不同长度的路径嵌入问题。我们证明了网络满足如下性质: 在s ≥ 3,t ≥ 3的条件下,对中任意两个不同顶点,长度在max{9,「s+1/2」+「t+1/2」+4}和2s+t+1-1之间的所有路径都能以膨胀率1嵌入到网络中,其中网络的直径为「s+1/2」+「t+1/2」+2。这里最优是指嵌入路径的膨胀率都是1。该结果表明:在相同维度下,尽管网络仅有交叉立方体网络中约一半的边数,但它在一定程度上依然保持了较好的路径嵌入能力。
关键词互连网络   交换交叉立方体   路径嵌入   并行计算机系统     
Abstract: The (s + t +1)-dimensional exchanged crossed cube, denoted as ECQ(s, t), combines the strong points of the exchanged hypercube and the crossed cube. It has been proven that ECQ(s, t) has more attractive properties than other variations of the fundamental hypercube in terms of fewer edges, lower cost factor and smaller diameter. In this paper, we study the embedding of paths of distinct lengths between any two different vertices in ECQ(s, t). We prove the result in ECQ(s, t): if s > 3, t > 3, for any two different vertices, all paths whose lengths are between max{9, 「s+1/2」+「t+1/2」+4} and 2s+t+1-1 can be embedded between the two vertices with dilation 1. Note that the diameter of ECQ(s, t) is s+1/2」+「t+1/2」+2. The obtained result is optimal in the sense that the dilations of path embeddings are all 1. The result reveals the fact that ECQ(s, t) preserves the path embedding capability to a large extent, while it only has about one half edges of CQn.
Keywordsinterconnection network   exchanged crossed cube   path embedding   parallel computing system     
Received 2016-04-21;
本文基金:

This work is supported by the National Natural Science Foundation of China under Grant Nos. 61572337 and 61502328, the Program for Postgraduates Research Innovation in University of Jiangsu Province under Grant No. KYLX160126, Collaborative Innovation Center of Novel Software Technology and Industrialization, and the Natural Science Foundation of the Jiangsu Higher Education Institutions of China under Grant No. 14KJB520034.

通讯作者: Jian-Xi Fan     Email: jxfan@suda.edu.cn
About author: Dong-Fang Zhou received his B.S. and M.S. degrees in computer science from Huaibei Normal University, Huaibei, and University of Science and Technology of China, Hefei, in 2005 and 2012, respectively. At present, He is a Ph.D. candidate at the School of Computer Science and Technology of Soochow University, Suzhou. His research interests include computer networks, parallel and distributed systems, interconnection architectures, and cloud computing.
引用本文:   
Dong-Fang Zhou, Jian-Xi Fan, Cheng-Kuan Lin, Bao-Lei Cheng, Jing-Ya Zhou, Zhao Liu.交换交叉立方体中最优路径的嵌入[J]  Journal of Computer Science and Technology , 2017,V32(3): 618-629
Dong-Fang Zhou, Jian-Xi Fan, Cheng-Kuan Lin, Bao-Lei Cheng, Jing-Ya Zhou, Zhao Liu.Optimal Path Embedding in the Exchanged Crossed Cube[J]  Journal of Computer Science and Technology, 2017,V32(3): 618-629
链接本文:  
http://jcst.ict.ac.cn:8080/jcst/CN/10.1007/s11390-017-1729-8
Copyright 2010 by Journal of Computer Science and Technology