›› 2017, Vol. 32 ›› Issue (3): 618-629.doi: 10.1007/s11390-017-1729-8

Special Issue: Computer Architecture and Systems; Artificial Intelligence and Pattern Recognition

• Theory and Algorithms • 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. 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
  • Received:2016-04-21 Revised:2016-12-23 Online:2017-05-05 Published:2017-05-05
  • Contact: Jian-Xi Fan E-mail: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.
  • Supported by:

    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.

PDF

813

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.

[1] Efe K. The crossed cube architecture for parallel computation. IEEE Transactions on Parallel and Distributed Systems, 1992, 3(5): 513-524.

[2] Chang C P, Sung T Y, Hsu L H. Edge congestion and topological properties of crossed cubes. IEEE Transactions on Parallel and Distributed Systems, 2000, 11(1): 64-80.

[3] Loh P K K, Hsu W J, Pan Y. The exchanged hypercube. IEEE Transactions on Parallel and Distributed Systems, 2005, 16(9): 866-874.

[4] Li K Q, Mu Y P, Li K Q, Min G Y. Exchanged crossed cube: A novel interconnection network for parallel computation. IEEE Transactions on Parallel and Distributed Systems, 2013, 24(11): 2211-2219.

[5] Ning W T. The super connectivity of exchanged crossed cube. Information Processing Letters, 2016, 116(2): 80-84.

[6] Ning W T, Feng X L, Wang L. The connectivity of exchanged crossed cube. Information Processing Letters, 2015, 115(2): 394-396.

[7] Auletta L, Rescigno A A, Scarano V. Embedding graphs onto the supercube. IEEE Transactions on Computers, 1995, 44(4): 593-597.

[8] Hsu H C, Li T K, Tan J J, Hsu L H. Fault hamiltonicity and fault hamiltonian connectivity of the arrangement graphs. IEEE Transactions on Computers, 2004, 53(1): 39-53.

[9] Kulasinghe P, Bettayeb S. Embedding binary trees into crossed cubes. IEEE Transactions on Computers, 1995, 44(7): 923-929.

[10] Patel A, Kusalik A, McCrosky C. Area-efficient VLSI layouts for binary hypercubes. IEEE Transactions on Computers, 2000, 49(2): 160-169.

[11] Chaudhary V, Aggarwal J K. A generalized scheme for mapping parallel algorithms. IEEE Transactions on Parallel and Distributed Systems, 1993, 4(3): 328-346.

[12] Cheng D, Hao R X, Feng Y Q. Embedding even cycles on folded hypercubes with conditional faulty edges. Information Processing Letters, 2015, 115(12): 945-949.

[13] Fan J X, Jia X H. Embedding meshes into crossed cubes. Information Sciences, 2007, 177(15): 3151-3160.

[14] Fan J X, Jia X H, Lin X L. Complete path embeddings in crossed cubes. Information Sciences, 2006, 176(22): 3332- 3346.

[15] Fan J X, Lin X L, Jia X H. Optimal path embedding in crossed cubes. IEEE Transactions on Parallel and Distributed Systems, 2005, 16(12): 1190-1200.

[16] Fu J S. Longest fault-free paths in hypercubes with vertex faults. Information Sciences, 2006, 176(7): 759-771.

[17] Kao S S, Lin C K, Huang H M, Hsu L H. Pancyclicity, panconnectivity, and panpositionability for general graphs and bipartite graphs. Ars Combinatoria, 2012, 105(105): 231-246.

[18] Tsai P Y, Lin Y T. Cycle embedding in alternating group graphs with faulty elements. In Proc. the 8th HumanCom and EMC, Aug. 2013, p.1281.

[19] Tsai C H, Lai C J. A linear algorithm for embedding of cycles in crossed cubes with edge-pancyclic. Journal of Information Science and Engineering, 2015, 31(4): 1347-1355.

[20] Wang D J. Hamiltonian embedding in crossed cubes with failed links. IEEE Transactions on Parallel and Distributed Systems, 2012, 23(11): 2117-2124.

[21] Andrews M, Chuzhoy J, Guruswami V, Khanna, S, Talwar, K, Zhang L S. Inapproximability of edge-disjoint paths and low congestion routing on undirected graphs. Combinatorica, 2010, 30(5): 485-520.

[22] Wu R Y, Chen G H, Kuo Y L, Chang G J. Node-disjoint paths in hierarchical hypercube networks. Information Sciences, 2007, 177(19): 4200-4207.

[23] Lai P L, Hsu H C. Constructing the nearly shortest path in crossed cubes. Information Sciences, 2009, 179(14): 2487- 2493.

[24] Boppana R V, Chalasani S, Raghavendra C S. Resource deadlocks and performance of wormhole multicast routing algorithms. IEEE Transactions on Parallel and Distributed Systems, 1998, 9(6): 535-549.

[25] Huang W T, Chuang Y C, Tan J J M et al. On the faulttolerant hamiltonicity of faulty crossed cubes. IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences, 2002, E85-A(6): 1359-1370.

[26] Chang T W, Navrátil O, Peng S L. The end-to-end longest path problem on a mesh with a missing vertex. Frontiers in Artificial Intelligence and Applications, 2015, 274: 59-66.

[27] Fan J X, Lin X L, Pan Y, Jia X H. Optimal fault-tolerant embedding of paths in twisted cubes. Journal of Parallel and Distributed Computing, 2007, 67(2): 205-214.

[28] Hsieh S Y. Embedding longest fault-free paths onto star graphs with more vertex faults. Theoretical Computer Science, 2005, 337(1/2/3): 370-378.

[29] Hsieh S Y, Chang N W. Hamiltonian path embedding and pancyclicity on the Möbius cube with faulty nodes and faulty edges. IEEE Transactions on Computers, 2006, 55(7): 854-863.

[30] Hsieh S Y, Lin T J. Panconnectivity and edge-pancyclicity of k-ary n-cubes. Networks, 2009, 54(1): 1-11.

[31] Lin M, Liu H M. Paths and cycles embedding on faulty enhanced hypercube networks. Acta Mathematica Scientia, 2013, 33(1): 227-246.

[32] Ma M J, Liu G Z, Xu J M. Fault-tolerant embedding of paths in crossed cubes. Theoretical Computer Science, 2008, 407(1/2/3): 110-116.

[33] Tsai C H, Jiang S Y. Path bipancyclicity of hypercubes. Information Processing Letters, 2007, 101(3): 93-97.

[34] Xu J M, Ma M J. Survey on path and cycle embedding in some networks. Frontiers of Mathematics in China, 2009, 4(2): 217-252.

[35] Bondy J A, Murty U S R. Graph Theory with Applications. Citeseer Publisher, 1976.

[36] Zhou D F, Fan J X, Lin C K, Zhou J Y, Wang X. Cycles embedding in exchanged crossed cube. International Journal of Foundations of Computer Science, 2017, 28(1): 61-76.
No related articles found!
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] Zhang Cui; Zhao Qinping; Xu Jiafu;. Kernel Language KLND[J]. , 1986, 1(3): 65 -79 .
[2] Lu Xuemiao;. On the Complexity of Induction of Structural Descriptions[J]. , 1987, 2(1): 12 -21 .
[3] Zhu Mingyuan;. Two Congruent Semantics for Prolog with CUT[J]. , 1990, 5(1): 82 -91 .
[4] Yang Hongqing;. A Characterization of Achievable Patterns of the MN-Puzzle Problem[J]. , 1990, 5(3): 266 -274 .
[5] Han Jianchao; Shi Zhongzhi;. Formalizing Default Reasoning[J]. , 1990, 5(4): 374 -378 .
[6] NIE Xumin; GUO Qing;. Renaming a Set of Non-Horn Clauses[J]. , 2000, 15(5): 409 -415 .
[7] ZHANG Yaoxue; WANG Xiaochun; GU Jun;. An End-to-End QoS Control Model for Enhanced Internet[J]. , 2000, 15(6): 497 -508 .
[8] Chen-Dong Xu and Fa-Lai Chen. Blending Canal Surfaces Based on PH Curves[J]. , 2005, 20(3): 389 -395 .
[9] Ruo-Chen Liu, Li-Cheng Jiao, and Hai-Feng Du. Clonal Strategy Algorithm Based on the Immune Memory[J]. , 2005, 20(5): 728 -734 .
[10] Kwang-Jin Park, Moon-Bae Song, and Chong-Sun Hwang. Broadcast-Based Spatial Queries[J]. , 2005, 20(6): 811 -821 .

ISSN 1000-9000(Print)

         1860-4749(Online)
CN 11-2296/TP

 Home
Editorial Board
Author Guidelines
Subscription		 Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
Tel.:86-10-62610746
E-mail: jcst@ict.ac.cn
 
  Copyright ©2015 JCST, All Rights Reserved