Abstract
Graph embeddings are not only used to study the simulation capabilities of a parallel architecture but also to design its VLSI layout. The n-dimensional hypercube is one of the most popular topological structure for interconnection networks in parallel computing and communication systems. The exchanged hypercube \(EH_{s,t}\) (where \(s\ge 1\) and \(t\ge 1\)) is obtained by systematically deleting edges from a hypercube \(Q_{s+t+1}\), which retains several valuable and desirable properties of the hypercube such as a small diameter, bipancyclicity, and super connectivity. In this paper, we identify maximum induced subgraph of \(EH_{s,t}\) and study embeddings of \(EH_{s,t}\) into a ring and a ladder with minimum wirelength.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Arockiaraj, M., Abraham, J., Quadras., J.: Linear layout of locally twisted cubes. Int. J. Comput. Math. 94(1), 56–65 (2017)
Bezrukov, S.L., Das, S.K., Elsasser, R.: An edge-isoperimetric problem for powers of the Petersen graph. Ann. Combinatorics 4(2), 153–169 (2000)
Bezrukov, S.L., Chavez, J.D., Harper, L.H., Röttger, M., Schroeder, U.P.: Embedding of hypercubes into grids. Mortar Fire Control System, pp. 693–701 (1998)
Boals, A.J., Gupta, A.K., Sherwani, N.A.: Incomplete hypercubes: algorithms and embeddings. J. Supercomputing 8(3), 263–294 (1994)
Chen, Y., Shen, H.: Routing and wavelength assignment for hypercube in array-based WDM optical networks. J. Parallel Distrib. Comput. 70(1), 59–68 (2010)
Erbele, J., Chavez, J., Trapp, R.: The cyclic cutwidth of \(Q_{n}\). Technical report, California State UniversitySan Bernardino (CSUSB) (2003)
Fan, J., Jia, X., Lin, X.: Complete path embeddings in crossed cubes. Inf. Sci. 176(22), 3332–3346 (2006)
Fan, J., Jia, X., Lin, X.: Embedding of cycles in twisted cubes with edge-pancyclic. Algorithmica 51(3), 264–282 (2008)
Wang, X., Fan, J., Jia, X.: Embedding meshes into twisted-cubes. Inf. Sci. 181(14), 3085–3099 (2011)
Garey, M.R., Johnson, D.S.: Computers and intractability: a guide to the theory of NP-completeness (1979)
Harper, L.H.: Global Methods for Combinatorial Isoperimetric Problems. Cambridge University Press, UK (2004)
Han, Y., Fan, J., Zhang, S.: Embedding meshes into locally twisted cubes. Inf. Sci. 180(19), 3794–3805 (2010)
Huang, K.E., Wu, J.: Area efficient layout of balanced hypercubes. Int. J. High Speed Electron. Syst. 6(04), 631–645 (1995)
Hsu, L.-H., Lin, C.-K.: Graph Theory and Interconnection Networks. CRC, Boca Raton (2008)
Liu, Y.-L., Wu, R.-C.: Implementing exchanged hypercube communication patterns on ring-connected WDM optical networks. IEICE Trans. Inf. Syst. 100(12), 2771–2780 (2017)
Loh, P.K.K., Hsu, W.-J., Pan, Y.: The exchanged hypercube. IEEE Trans. Parallel Distrib. Syst. 16(9), 866–874 (2005)
Katseff, H.: Incomplete hypercubes. IEEE Trans. Comput. 37(5), 604–608 (1988)
Ma, M., Liu, B.: Cycles embedding in exchanged hypercubes. Inf. Process. Lett. 110(2), 71–76 (2009)
Manuel, P., Rajasingh, I., Rajan, B.: Exact wirelength of hypercubes on a grid. Discrete Appl. Math. 157(7), 1486–1495 (2009)
Ma, M., Zhu, L.: The super connectivity of exchanged hypercubes. Inf. Process. Lett. 111(8), 360–364 (2011)
Miller, M., Rajan, R.S., Parthiban, N.: Minimum linear arrangement of incomplete hypercubes. Comput. J. 58(2), 331–337 (2015)
Nakano, K.: Linear layout of generalized hypercubes. Int. J. Found. Comput. Sci. 14(01), 137–156 (2003)
Rostami, H., Habibi, J.: Minimum linear arrangement of Chord graphs. Appl. Math. Comput. 203(1), 358–367 (2008)
Sýkora, O., Vrt’o, I.: On VLSI layouts of the star graph and related networks. Integr. VLSI J. 17(1), 83–93 (1994)
Wan, L., Liu., Y.: On the embedding genus distribution of ladders and crosses. Appl. Math. Lett. 22(5) 738–742 (2009)
Wang, D.: Hamiltonian embedding in crossed cubes with failed links. IEEE Trans. Parallel Distrib. Syst. 23(11), 2117–2124 (2012)
Wang, S., Zhang, S.: Embedding hamiltonian paths in \(k\)-ary \(n\)-cubes with conditional edge faults. Theoret. Comput. Sci. 412(46), 6570–6584 (2011)
Yang, Y., Li, J., Wang, S.: Embedding various cycles with prescribed paths into \(k\)-ary \(n\)-cubes. Discrete Appl. Math. 220, 161–169 (2017)
Yang, X., David, J.E., Graham, M.: Maximum induced subgraph of a recursive circulant. Inf. Process. Lett. 95(1), 293–298 (2005)
Yeh, C. H., Varvarigos, E. A., Parhami, B.: Multilayer VLSI layout for interconnection networks. In: Proceedings of International Conference on IEEE Parallel Processing, pp. 33–40 (2000)
Yu, C., Yang, X.: Routing and wavelength assignment for 3-ary \(n\)-cube in array-based optical network. Inf. Process. Lett. 112(6), 252–256 (2012)
Acknowledgment
We would like to express our sincerest appreciation to Prof. Guoliang Chen for his constructive suggestions. This work is supported by National Key R&D Program of China (2018YFB1003201), Natural Science Foundation of China under grant (No. 61572337, No. 61602333, No. 61672296 and No. 61702351), China Postdoctoral Science Foundation (No. 172985), Scientific & Technological Support Project of Jiangsu Province (No. BE2016777, No. BE2016185), Natural Science Foundation of the Jiangsu Higher Education Institutions of China (Nos. 17KJB520036), Jiangsu Planned Projects for Postdoctoral Research Funds under Grant (No. 1701172B) and Jiangsu High Technology Research Key Laboratory for Wireless Sensor Networks Foundation (No. WSNLBKF201701).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 Springer Nature Switzerland AG
About this paper
Cite this paper
Fan, W., Fan, J., Lin, CK., Han, Z., Li, P., Wang, R. (2018). Embedding Exchanged Hypercubes into Rings and Ladders. In: Vaidya, J., Li, J. (eds) Algorithms and Architectures for Parallel Processing. ICA3PP 2018. Lecture Notes in Computer Science(), vol 11335. Springer, Cham. https://doi.org/10.1007/978-3-030-05054-2_1
Download citation
DOI: https://doi.org/10.1007/978-3-030-05054-2_1
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-05053-5
Online ISBN: 978-3-030-05054-2
eBook Packages: Computer ScienceComputer Science (R0)