? Optimal Path Embedding in the Exchanged Crossed Cube
Journal of Computer Science and Technology
Quick Search in JCST
 Advanced Search 
      Home | PrePrint | SiteMap | Contact Us | FAQ
 
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 Current Issue | Archive | Adv Search << Previous Articles | Next Articles >>
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

Abstract
Reference
Related Articles
Download: [PDF 443KB]     Export: BibTeX or EndNote (RIS)  
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.
Articles by authors
Dong-Fang Zhou
Jian-Xi Fan
Cheng-Kuan Lin
Bao-Lei Cheng
Jing-Ya Zhou
Zhao Liu
Keywordsinterconnection network   exchanged crossed cube   path embedding   parallel computing system     
Received 2016-04-21;
Fund:

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.

Corresponding Authors: 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.
Cite this article:   
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
URL:  
http://jcst.ict.ac.cn:8080/jcst/EN/10.1007/s11390-017-1729-8
Copyright 2010 by Journal of Computer Science and Technology