Embedding complete multi-partite graphs into Cartesian product of paths and cycles
Abstract
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.
Keywords
Full Text:
PDFDOI: http://dx.doi.org/10.5614/ejgta.2021.9.2.21
References
D. Adolphson and T.C. Hu, Optimal linear ordering, SIAM J Appl Math. 25, 403–423, 1973.
M. Arockiaraj, J.N. Delaila, and J. Abraham, Optimal wirelength of balanced complete multipartite graphs onto cartesian product of {Path, Cycle} and trees, Fundam. Inform. 178 (2021), 187-202.
L. Auletta, A.A. Rescigno, and V. Scarano, Embedding graphs onto the supercube, IEEE Trans Comput. 44 (1995), 593–597.
S.L. Bezrukov, J.D. Chavez, L.H. Harper, M. Rottger and U.P. Schroeder, Embedding of hypercubes into grids, MFCS. Lect. Notes Comput. Sci. 1450 (1998), 693–701.
S.L. Bezrukov, S.K. Das and R. Elsasser, An edge-isoperimetric problem for powers of the Petersen graph, Ann. Comb. 4 (2000), 153–169.
S.L. Bezrukov and U.-P. Schroeder, The cyclic wirelength of trees, Discret. Appl. Math. 87 (1998), 275–277.
M.Y. Chan, Embedding of grids into optimal hypercubes, SIAM J. Comput. 20 (1991), 834–864.
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.
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.
B. Cheng, D. Wang, and J. Fan, Constructing completely independent spanning trees in crossed cubes, Discret. Appl. Math. 219 (2017), 100-109.
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.
S.A. Choudum and U. Nahdini, Complete binary trees in folded and enhanced cubes, Networks, 43 (2004), 266–272.
J. Diaz, J. Petit, and M. Serna, A Survey of Graph Layout Problems, ACM Comput. Surv. 34 (2002), 313–356.
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.
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.
J.-F. Fang and K.-C. Lai, Embedding the incomplete hypercube in books, Inf. Process. Lett. 96 (2005), 1–6.
M.R. Garey and D.S. Johnson, Computers and Intractability, A Guide to the Theory of NP Completeness, Freeman, San Francisco, (1979).
C.-J. Guu, The Circular Wirelength Problem for Hypercubes, Ph.D. dissertation, University of California, Riverside, (1997).
L.H. Harper, Global Methods for Combinatorial Isoperimetric Problems, Cambridge University Press, (2004).
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.
P. Kulasinghe and S. Bettayeb, Embedding binary trees into crossed cubes, IEEE Trans Comput. 44 (1995), 923–929.
K.J. Kumar, S. Klavzˇar, R.S. Rajan, I. Rajasingh and T.M. Rajalaxmi, An asymptotic relation between the wirelength of an embedding and the Wiener index, Discrete Math. Lett., to appear.
P.L. Lai and C.-H. Tsai, Embedding of tori and grids into twisted cubes, Theor. Comput. Sci. 411 (2010), 3763–3773.
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.
P. Manuel, I. Rajasingh, B. Rajan, and H. Mercy, Exact wirelength of hypercube on a grid, Discrete. Appl. Math. 157 (2009), 1486–1495.
R.S. Mary and I. Rajasingh, Embedding of complete graphs and cycles into grids with holes, Procedia Comput. Sci. 172 (2020), 115–121.
M. Miller, R.S. Rajan, N. Parthiban, and I. Rajasingh, Minimum linear arrangement of incomplete hypercubes, J. Comput. 58 (2015), 331–337.
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).
R.S. Rajan, T. Kalinowski, S. Klavzˇar, H. Mokhtar, and T.M. Rajalaxmi, Lower bounds for dilation, Wirelength, and edge Congestion of embedding graphs into hypercubes, J Supercomput. 77 (2021), 4135-4150.
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.
Refbacks
- There are currently no refbacks.
ISSN: 2338-2287
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.