On the optimal layout of balanced complete multipartite graphs into grids and tree related structures. (English) Zbl 1451.05155
Summary: An interconnection network is a complex connection of a set of processors and communication links between different processors which is utilized to exchange data between processors in the parallel computing system. Graph embedding is a vital tool used to run parallel algorithms in computer networks in which placing different modules on the board is one of the main cost criteria. By finding the optimal layout, the placement problem in circuit designs which does not have any deterministic algorithms can be solved. The complete multipartite graph is a widely used network topology with a high degree of reliability due to its flexible choice of network size. Recently a study was made by computing the optimal layout of balanced complete multipartite graphs into host graphs taken from the Cartesian product of elements in the set {path, cycle}, but leaving the case of product of paths as an open problem. This paper aims to solve such an open problem and the key idea is to locate suitable optimal sets in balanced complete multipartite graphs with respect to maximizing the number of edges in the located sets. Besides, we compute the layout in the case of host graphs like \(k\)-rooted complete binary trees, \(k\)-rooted sibling trees and the Cartesian product of path \(P_2\) and complete binary trees.
MSC:
| 05C62 | Graph representations (geometric and intersection representations, etc.) |
| 05C05 | Trees |
| 05C82 | Small world graphs, complex networks (graph-theoretic aspects) |
| 05C76 | Graph operations (line graphs, products, etc.) |
| 68R10 | Graph theory (including graph drawing) in computer science |
| 68M10 | Network design and communication in computer systems |
References:
| [1] | M. Arockiaraj, J. Abraham, A.J. Shalini, Node set optimization problem for complete Josephus cubes, J. Comb. Optim. http://dx.doi.org/10.1007/s10878-019-00443-9. · Zbl 1432.90152 |
| [2] | Arockiaraj, M.; Manuel, P.; Rajasingh, I.; Rajan, B., Wirelength of 1-fault Hamiltonian graphs into wheels and fans, Inf. Process. Lett., 111, 8, 921-925 (2011) · Zbl 1260.68291 |
| [3] | Arockiaraj, M.; Quadras, J.; Rajasingh, I.; Shalini, A. J., Embedding hypercubes and folded hypercubes onto Cartesian product of certain trees, Discrete Optim., 17, 1-13 (2015) · Zbl 1387.68176 |
| [4] | Arockiaraj, M.; Shalini, A. J., Conjectures on wirelength of hypercube into cylinder and torus, Theoret. Comput. Sci., 595, 168-171 (2015) · Zbl 1328.68143 |
| [5] | Bezrukov, S. L.; Chavez, J. D.; Harper, L. H.; Röttger, M.; Schroeder, U. P., The congestion of n-cube layout on a rectangular grid, Discrete Math., 213, 1, 13-19 (2000) · Zbl 0953.68115 |
| [6] | Bezrukov, S. L.; Das, S. K.; Elsässer, R., An edge-isoperimetric problem for powers of the Petersen graph, Ann. Comb., 4, 2, 153-169 (2000) · Zbl 0951.05053 |
| [7] | Chelvam, T. T.; Raja, S.; Gutman, I., Strongly regular integral circulant graphs and their energies, Bull. Int. Math. Virt. Inst., 2, 9-16 (2012) · Zbl 1451.05137 |
| [8] | Díaz, J.; Petit, J.; Serna, M., A survey of graph layout problems, ACM Comput. Surv., 34, 3, 313-356 (2002) |
| [9] | Fan, W.; Fan, J.; Lin, C. K.; Wang, G.; Cheng, B.; Wang, R., An efficient algorithm for embedding exchanged hypercubes into grids, J. Supercomput., 75, 2, 783-807 (2019) |
| [10] | Fan, W.; Fan, J.; Lin, C. K.; Wang, Y.; Han, Y.; Wang, R., Optimally embedding 3-ary n-cubes into grids, J. Comput. Sci. Technol., 34, 2, 372-387 (2019) |
| [11] | Goyal, P.; Ferrara, E., Graph embedding techniques, applications, and performance: A survey, Knowl.-Based Syst., 151, 78-94 (2018) |
| [12] | Greeni, A. B.; Rajasingh, I., Embedding complete bipartite graph into grid with optimum congestion and wirelength, Int. J. Netw. Virtual Organ., 17, 1, 64-75 (2017) |
| [13] | Lai, Y. L.; Williams, K., A survey of solved problems and applications on bandwidth, edgesum, and profile of graphs, J. Graph Theory, 31, 2, 75-94 (1999) · Zbl 0924.05058 |
| [14] | Liu, J. B.; Arockiaraj, M.; Delaila, J. N., Wirelength of enhanced hypercube into windmill and necklace graphs, Mathematics, 7, 5, 383 (2019) |
| [15] | Manuel, P.; Rajasingh, I.; Rajan, B.; Mercy, H., Exact wirelength of hypercubes on a grid, Discrete Appl. Math., 157, 7, 1486-1495 (2009) · Zbl 1172.05330 |
| [16] | Muradian, D., On Three Graph Layout Problems (2018), Lap Lambert Academic Publishing: Lap Lambert Academic Publishing Mauritius |
| [17] | Muradian, D.; Piliposyan, T., Minimal linear arrangement and cutwidth problems for complete n-partite graphs, Uchen. Zap. Erevan. Gosuniv., 144, 2, 18-26 (1980), (in Russian) |
| [18] | R.S. Rajan, T.M. Rajalaxmi, J.B. Liu, G. Sethuraman, Wirelength of embedding complete multipartite graphs into certain graphs, Discrete Appl. Math. http://dx.doi.org/10.1016/j.dam.2018.05.034. · Zbl 1439.05162 |
| [19] | Rajan, R. S.; Shantrinal, A. A.; Kumar, K. J.; Rajalaxmi, T. M.; Fan, J.; Fan, W., Embedding complete multi-partite graphs into cartesian product of paths and cycles (2019), arXiv:1901.07717v1 [math.CO] |
| [20] | Rajasingh, I.; Manuel, P.; Rajan, B.; Arockiaraj, M., Wirelength of hypercubes into certain trees, Discrete Appl. Math., 160, 18, 2778-2786 (2012) · Zbl 1253.68265 |
| [21] | Rajasingh, I.; William, A.; Quadras, J.; Manuel, P., Embedding of cycles and wheels into arbitrary trees, Networks, 44, 3, 173-178 (2004) · Zbl 1056.05042 |
| [22] | A.J. Shalini, J. Abraham, M. Arockiaraj, A linear time algorithm for embedding locally twisted cube into grid network to optimize the layout, Discrete Appl. Math. http://dx.doi.org/10.1016/j.dam.2018.06.039. · Zbl 1447.05070 |
| [23] | Shantrinal, A. A.; Rajan, R. S.; Babu, A. R.; Anil, S.; Ahmed, M. A., Embedding complete multipartite graphs into certain trees (2019), arXiv:1910.10643v1 [math.CO] [Accepted in J. Comb. Math. Comb. Comput.] |
| [24] | Xu, J., Topological Structure and Analysis of Interconnection Networks (2001), Springer Publishing Company: Springer Publishing Company Dordrecht · 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.
