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 \left\{9,\left\lceil \frac{s+1}{2}\right\rceil +\left\lceil \frac{t+1}{2}\right\rceil +4\right\} \) and 2s+t+1 − 1 can be embedded between the two vertices with dilation 1. Note that the diameter of ECQ(s, t) is \( \left\lceil \frac{s+1}{2}\right\rceil +\left\lceil \frac{t+1}{2}\right\rceil +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 CQ n .
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Efe K. The crossed cube architecture for parallel computation. IEEE Transactions on Parallel and Distributed Systems, 1992, 3(5): 513-524.
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.
Loh P K K, Hsu W J, Pan Y. The exchanged hypercube. IEEE Transactions on Parallel and Distributed Systems, 2005, 16(9): 866-874.
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.
Ning W T. The super connectivity of exchanged crossed cube. Information Processing Letters, 2016, 116(2): 80-84.
Ning W T, Feng X L, Wang L. The connectivity of exchanged crossed cube. Information Processing Letters, 2015, 115(2): 394-396.
Auletta L, Rescigno A A, Scarano V. Embedding graphs onto the supercube. IEEE Transactions on Computers, 1995, 44(4): 593-597.
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.
Kulasinghe P, Bettayeb S. Embedding binary trees into crossed cubes. IEEE Transactions on Computers, 1995, 44(7): 923-929.
Patel A, Kusalik A, McCrosky C. Area-efficient VLSI layouts for binary hypercubes. IEEE Transactions on Computers, 2000, 49(2): 160-169.
Chaudhary V, Aggarwal J K. A generalized scheme for mapping parallel algorithms. IEEE Transactions on Parallel and Distributed Systems, 1993, 4(3): 328-346.
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.
Fan J X, Jia X H. Embedding meshes into crossed cubes. Information Sciences, 2007, 177(15): 3151-3160.
Fan J X, Jia X H, Lin X L. Complete path embeddings in crossed cubes. Information Sciences, 2006, 176(22): 3332-3346.
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.
Fu J S. Longest fault-free paths in hypercubes with vertex faults. Information Sciences, 2006, 176(7): 759-771.
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.
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.
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.
Wang D J. Hamiltonian embedding in crossed cubes with failed links. IEEE Transactions on Parallel and Distributed Systems, 2012, 23(11): 2117-2124.
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.
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.
Lai P L, Hsu H C. Constructing the nearly shortest path in crossed cubes. Information Sciences, 2009, 179(14): 2487-2493.
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.
Huang W T, Chuang Y C, Tan J J M et al. On the fault-tolerant hamiltonicity of faulty crossed cubes. IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences, 2002, E85-A(6): 1359-1370.
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.
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.
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.
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.
Hsieh S Y, Lin T J. Panconnectivity and edge-pancyclicity of k-ary n-cubes. Networks, 2009, 54(1): 1-11.
Lin M, Liu H M. Paths and cycles embedding on faulty enhanced hypercube networks. Acta Mathematica Scientia, 2013, 33(1): 227-246.
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.
Tsai C H, Jiang S Y. Path bipancyclicity of hypercubes. Information Processing Letters, 2007, 101(3): 93-97.
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.
Bondy J A, Murty U S R. Graph Theory with Applications. Citeseer Publisher, 1976.
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.
Author information
Authors and Affiliations
Corresponding author
Electronic supplementary material
Below is the link to the electronic supplementary material.
ESM 1
(PDF 476 kb)
Rights and permissions
About this article
Cite this article
Zhou, DF., Fan, JX., Lin, CK. et al. Optimal Path Embedding in the Exchanged Crossed Cube. J. Comput. Sci. Technol. 32, 618–629 (2017). https://doi.org/10.1007/s11390-017-1729-8
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11390-017-1729-8