Optimal Wirelength of Balanced Complete Multipartite Graphs onto Cartesian Product of {Path, Cycle} and Trees

• Autorzy: Arockiaraj Micheal , Delaila J. Nancy , Abraham Jessie

Identyfikatory

DOI

10.3233/FI-2021-2003

• Języki publikacji: EN

Abstrakty

EN

In any interconnection network, task allocation plays a major role in the processor speed as fair distribution leads to enhanced performance. Complete multipartite networks serve well for this purpose as the task can be split into different partites which improves the degree of reliability of the network. Such an allocation process in the network can be done by means of graph embedding. The optimal wirelength of a graph embedding helps in the distribution of deterministic algorithms from the guest graph to other host graphs in order to incorporate its unique deterministic properties on that chosen graph. In this paper, we propose an algorithm to compute the optimal wirelength of balanced complete multipartite graphs onto the Cartesian product of trees with path and cycle. Moreover, we derive the closed formulae for wirelengths in specific trees like (1-rooted) complete binary tree and sibling graphs.

Słowa kluczowe

EN

balanced complete t-partite graph; embedding; wirelength; Cartesian product

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2021
• Tom: Vol. 178, nr 3
• Strony: 187--202
• Opis fizyczny: Bibliogr. 21 poz., rys.

Twórcy

autor

Arockiaraj Micheal

• Department of Mathematics, Loyola College, Chennai 600034, India

autor

Delaila J. Nancy

• Department of Mathematics, Loyola College, University of Madras, Chennai 600034, India

autor

Abraham Jessie

• Department of Mathematics, KCG College of Technology, Chennai 600097, India

Bibliografia

• [1] Arockiaraj M, Quadras J, Rajasingh I, Shalini AJ. Embedding hypercubes and folded hypercubes onto Cartesian product of certain trees. Discrete Optimization, 2015. 17:1-13. doi:10.1016/j.disopt.2015.03.001.
• [2] Bezrukov S, Monien B, Unger W, Wechsung G. Embedding ladders and caterpillars into the hypercube. Discrete Applied Mathematics, 1998. 83(1-3):21-29. doi:10.1016/S0166-218X(97) 00101-7.
• [3] Bezrukov SL, Chavez JD, Harper LH, Röttger M, Schroeder UP. The congestion of n-cube layout on a rectangular grid. Discrete Mathematics, 2000. 213(1):13-19. doi:10.1016/S0012-365X(99)00162-4.
• [4] Díaz J, Petit J, Serna M. A survey of graph layout problems. ACM Computing Surveys (CSUR), 2002. 34(3):313-356. doi:10.1145/568522.568523.
• [5] Lai YL, Williams K. A survey of solved problems and applications on bandwidth, edgesum, and profile of graphs. Journal of Graph Theory, 1999. 31(2):75-94. doi:10.1002/(SICI)1097-0118(199906)31:2<75::AID-JGT1>3.0.CO;2-S.
• [6] Manuel P, Rajasingh I, Rajan B, Mercy H. Exact wirelength of hypercubes on a grid. Discrete Applied Mathematics, 2009. 157(7):1486-1495. doi:10.1016/j.dam.2008.09.013.
• [7] Arockiaraj M, Abraham J, Shalini AJ. Node set optimization problem for complete Josephus cubes. Journal of Combinatorial Optimization, 2019. 38(4):1180-1195. doi:10.1007/s10878-019-00443-9.
• [8] Parthiban N, Ryan J, Rajasingh I, Rajan RS, Rani LN. Exact wirelength of embedding chord graph into tree-based architectures. International Journal of Networking and Virtual Organisations, 2017. 17(1):76-87. doi:10.1504/IJNVO.2017.083547.
• [9] Rajan RS, Rajalaxmi TM, Liu JB, Sethuraman G. Wirelength of embedding complete multipartite graphs into certain graphs. Discrete Applied Mathematics, 2020. 280:221-236. doi:10.1016/j.dam.2018. 05.034.
• [10] Harper LH. Global methods for combinatorial isoperimetric problems. Cambridge University Press, 2004. ISBN:9780511616679. doi:10.1017/CBO9780511616679.
• [11] Arockiaraj M, Manuel P, Rajasingh I, Rajan B. Wirelength of 1-fault hamiltonian graphs into wheels and fans. Information Processing Letters, 2011. 111(8):921-925. doi:10.1016/j.ipl.2011.06.011.
• [12] Gethner E, Hogben L, Lidický B, Pfender F, Ruiz A, Young M. On crossing numbers of complete tripartite and balanced complete multipartite graphs. Journal of Graph Theory, 2017. 84(4):552-565. doi:10.1002/jgt.22041.
• [13] Burger AP, van Vuuren JH. Ramsey numbers in complete balanced multipartite graphs. Part II: Size numbers. Discrete Mathematics, 2004. 283(1-3):45-49. doi:10.1016/j.disc.2004.02.003.
• [14] Yen C, Fu H. Linear 3-arboricity of the balanced complete multipartite graphs. Journal of Combinatorial Mathematics and Combinatorial Computing, 2007. 60:33-46.
• [15] Arockiaraj M, Liu JB, Delaila JN, Shalini A. On the optimal layout of balanced complete multipartite graphs into grids and tree related structures. Discrete Applied Mathematics, 2021. 288:50-65. doi:10.1016/j.dam.2020.08.022.
• [16] Rajan RS, Shantrinal AA, Kumar KJ, Rajalaxmi TM, Fan J, Fan W. Embedding complete multi-partite graphs into Cartesian product of paths and cycles. 2019. arXiv preprint, arXiv:1901.07717.
• [17] Muradian D. On three graph layout problems. Lap Lambert Academic Publishing, Mauritius, 2018. ISBN:978-620-2-05385-3.
• [18] Muradyan DO, Piliposyan TE. The problem of finding the length and width of the complete p-partite graph (in Russian). Fluchen. Zapiski Erevan. Gosunivers, 1980. 144(2):18-26.
• [19] Abraham J, Arockiaraj M. Layout of embedding locally twisted cube into the extended theta mesh topology. Electronic Notes in Discrete Mathematics, 2017. 63:373-379. doi:10.1016/j.endm.2017.11.034.
• [20] Imrich W, Klavzar S. Product graphs: structure and recognition. Wiley, 2000. ISBN:978-0471370390.
• [21] Arockiaraj M, Kavitha SRJ, Balasubramanian K. Vertex cut method for degree and distance-based topological indices and its applications to silicate networks. Journal of Mathematical Chemistry, 2016. 54(8):1728-1747. doi:10.1007/s10910-016-0646-3.

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2021).