Embedding complete multi-partite graphs into Cartesian product of paths and cycles. (English) Zbl 1482.05238
Summary: Graph embedding is a powerful method in parallel computing that maps a guest network \(G\) into a host network \(H\). The performance of an embedding can be evaluated by certain parameters, such as the dilation, the edge congestion, and the wirelength. In this manuscript, we obtain the wirelength (exact and minimum) of embedding complete multi-partite graphs into Cartesian product of paths and/or cycles, which include \(n\)-cube, \(n\)-dimensional mesh (grid), \(n\)-dimensional cylinder, and \(n\)-dimensional torus, etc., as the subfamilies.
MSC:
| 05C60 | Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) |
| 05C85 | Graph algorithms (graph-theoretic aspects) |
| 05C76 | Graph operations (line graphs, products, etc.) |
| 05C38 | Paths and cycles |
Keywords:
embedding; edge congestion; wirelength; complete multi-partite graphs; Cartesian product of graphsReferences:
| [1] | D. Adolphson and T.C. Hu, Optimal linear ordering, SIAM J. Appl Math. 25, 403-423, 1973. · Zbl 0274.90061 |
| [2] | M. Arockiaraj, J.N. Delaila, and J. Abraham, Optimal wirelength of balanced complete multi-partite graphs onto cartesian product of {Path, Cycle} and trees, Fundam. Inform. 178 (2021), 187-202. · Zbl 1482.68169 |
| [3] | L. Auletta, A.A. Rescigno, and V. Scarano, Embedding graphs onto the supercube, IEEE Trans Comput. 44 (1995), 593-597. · Zbl 1040.68541 |
| [4] | S.L. Bezrukov, J.D. Chavez, L.H. Harper, M. Röttger, and U.P. Schroeder, Embedding of hypercubes into grids, MFCS. Lect. Notes Comput. Sci. 1450 (1998), 693-701. |
| [5] | S.L. Bezrukov, S.K. Das, and R. Elsässer, An edge-isoperimetric problem for powers of the Petersen graph, Ann. Comb. 4 (2000), 153-169. · Zbl 0951.05053 |
| [6] | S.L. Bezrukov and U.P. Schroeder, The cyclic wirelength of trees, Discrete. Appl. Math. 87 (1998), 275-277. · Zbl 0908.05056 |
| [7] | M.Y. Chan, Embedding of grids into optimal hypercubes, SIAM J. Comput. 20 (1991), 834-864. · Zbl 0731.68011 |
| [8] | M.Y. Chan and S.J. Lee, Fault-tolerant embedding of complete binary trees in hypercubes, IEEE Trans Parallel Distrib Syst. 4 (1993), 277-288. |
| [9] | B. Cheng, J. Fan, and X. Jia, Dimensional-Permutation-Based independent spanning trees in bijective connection networks, IEEE Trans Parallel Distrib Syst. 26 (2015), 45-53. |
| [10] | B. Cheng, D. Wang, and J. Fan, Constructing completely independent spanning trees in crossed cubes, Discrete Appl. Math. 219 (2017), 100-109. · Zbl 1354.05026 |
| [11] | F.R.K. Chung, F.T. Leighton, and A.L. Rosenberg, Embedding graphs in books: A layout problem with applications to VLSI design, SIAM J. Alg. Discrete Math. 8 (1987), 33-58. · Zbl 0617.68062 |
| [12] | S.A. Choudum and U. Nahdini, Complete binary trees in folded and enhanced cubes, Net-works, 43 (2004), 266-272. · Zbl 1054.68098 |
| [13] | J. Diaz, J. Petit, and M. Serna, A Survey of Graph Layout Problems, ACM Comput. Surv. 34 (2002), 313-356. |
| [14] | J. Ellis, S. Chow, and D. Manke, Many to one embeddings from grids into cylinders, tori and hypercubes, SIAM J. Comput. 32 (2003), 386-407. · Zbl 1021.05026 |
| [15] | J. Fan, X. Lin, X. Jia, and R.W.H. Lau, Edge-Pancyclicity of twisted Cubes, (ISAAC). Lect. Notes Comput. Sci (LNCS). 3827 (2005), 1090-1099. · Zbl 1175.68291 |
| [16] | J.-F. Fang and K.-C. Lai, Embedding the incomplete hypercube in books, Inf. Process. Lett. 96 (2005), 1-6. · Zbl 1184.68100 |
| [17] | M.R. Garey and D.S. Johnson, Computers and Intractability, A Guide to the Theory of NP-Completeness, Freeman, San Francisco, (1979). · Zbl 0411.68039 |
| [18] | C.-J. Guu, The Circular Wirelength Problem for Hypercubes, Ph.D. dissertation, University of California, Riverside, (1997). |
| [19] | L.H. Harper, Global Methods for Combinatorial Isoperimetric Problems, Cambridge Univer-sity Press, (2004). · Zbl 1043.05002 |
| [20] | M.H. Khalifeh, H.Y.-Azari, and A.R. Ashrafi, The hyper-Wiener index of graph operations, Comput. Math. with Appl. 56 (2008), 1402-1407. · Zbl 1155.05316 |
| [21] | P. Kulasinghe, and S. Bettayeb, Embedding binary trees into crossed cubes, IEEE Trans Comput. 44 (1995), 923-929. · Zbl 1053.68585 |
| [22] | K.J. Kumar, S. Klavžar, R.S. Rajan, I. Rajasingh, and T.M. Rajalaxmi, An asymptotic rela-tion between the wirelength of an embedding and the wiener index, Discrete Math. Lett., to appear. · Zbl 1513.05096 |
| [23] | P.-L. Lai and C.-H. Tsai, Embedding of tori and grids into twisted cubes, Theor. Comput. Sci. 411 (2010), 3763-3773. · Zbl 1208.68047 |
| [24] | R.-S. Lo and G.-H. Chen, Embedding Hamiltonian paths in faulty arrangement graphs with the backtracking method, IEEE Trans Parallel Distrib Syst. 12 (2001), 209-222. |
| [25] | P. Manuel, I. Rajasingh, B. Rajan, and H. Mercy, Exact wirelength of hypercube on a grid, Discret. Appl. Math. 157 (2009), 1486-1495. · Zbl 1172.05330 |
| [26] | R.S. Mary and I. Rajasingh, Embedding of complete graphs and cycles into grids with holes, Procedia Comput. Sci. 172 (2020), 115-121. |
| [27] | M. Miller, R.S. Rajan, N. Parthiban, and I. Rajasingh, Minimum linear arrangement of in-complete hypercubes, J. Comput. 58 (2015), 331-337. |
| [28] | G.K. Nandini, R.S. Rajan, T.M. Rajalaxmi, A.A. Shantrinal, K.S.K. Sharifah, and H. Roslan, Wiener index via wirelength of an embedding, Discrete Math. Algorithms Appl. (2021). |
| [29] | R.S. Rajan, T. Kalinowski, S. Klavžar, H. Mokhtar, and T.M. Rajalaxmi, Lower bounds for dilation, Wirelength, and edge Congestion of embedding graphs into hypercubes, J Super-comput. 77 (2021), 4135-4150. |
| [30] | R.S. Rajan, T.M. Rajalaxmi, J.B. Liu, and G. Sethuraman, Wirelength of embedding complete multipartite graphs into certain graphs, Discrete Appl. Math. 280 (2020), 221-236. · Zbl 1439.05162 |
| [31] | R.S. Rajan, T.M. Rajalaxmi, S. Stephen, A.A. Shantrinal, and K. Jagadeesh Kumar, Embed-ding wheel-like networks, Iran. J. Math. Sci. Inform. (2020). |
| [32] | I. Rajasingh, M. Arockiaraj, B. Rajan, and P. Manuel, Minimum wirelength of hypercubes into n-dimensional grid networks, Inf. Process. Lett. 112 (2012), 583-586. · Zbl 1243.05127 |
| [33] | I. Rajasingh, J. Quadras, P. Manuel, and A. William, Embedding of cycles and wheels into arbitrary trees, Networks, 44 (2004), 173-178. · Zbl 1056.05042 |
| [34] | I. Rajasingh and R.S. Rajan, Exact wirelength of embedding circulant networks into necklace and windmill Graphs, Ars Comb. 130 (2017), 215-237. · Zbl 1413.05365 |
| [35] | I. Rajasingh, R.S. Rajan, and P. Manuel, A linear time algorithm for embedding Christmas trees into certain trees, Parallel Process. Lett. 25 (2015), 1-17. · Zbl 1376.68115 |
| [36] | I. Rajasingh, B. Rajan, and R.S. Rajan, Embedding of special classes of circulant networks, hypercubes and generalized Petersen graphs, Int. J. Comput. Math. 89 (2012), 1970-1978. · Zbl 1255.68040 |
| [37] | H. Rostami and J. Habibi, Minimum linear arrangement of chord graphs, Appl. Math. Com-put. 203 (2008), 358-367. · Zbl 1161.05343 |
| [38] | B.H. Susanti, A.N.M. Salman, and R. Simanjuntak, The rainbow 2-connectivity of Cartesian products of 2-connected graphs and paths, Electron. J. Graph Theory Appl. 8 (2020), 145-156. · Zbl 1468.05087 |
| [39] | Y.-C. Tseng, S.-H. Chang, and J.-P. Sheu, Fault-tolerant ring embedding in a star graph with both link and node failures, IEEE Trans Parallel Distrib Syst. 8 (1997), 1185-1195. |
| [40] | A. Wagner and D.G. Corneil, Embedding trees in a hypercube is np-complete, SIAM J. Com-put. 19 (1990), 570-590. · Zbl 0698.68054 |
| [41] | X. Wang, A. Erickson, J. Fan, and X. Jia, Hamiltonian properties of DCell networks, J. Comput. 58 (2015), 2944-2955. |
| [42] | M.-C. Yang, Path embedding in star graphs, Appl. Math. Comput. 207 (2009), 283-291. · Zbl 1163.05011 |
| [43] | X. Yang, Q. Dong, and Y.Y. Tan, Embedding meshes/tori in faulty crossed cubes, Inf. Process. Lett. 110 (2010), 559-564. · Zbl 1234.68021 |
| [44] | P.-J. Yang, S.-B. Tien, and C.S. Raghavendra, Embedding of rings and meshes onto faulty hypercubes using free dimensions, IEEE Trans. Comput. 43 (1994), 608-613. |
| [45] | J.M. Xu, Topological Structure and Analysis of Interconnection Networks, Kluwer Academic Publishers, (2001). · Zbl 1046.68026 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
