PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
Tytuł artykułu

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

Wybrane pełne teksty z tego czasopisma
Identyfikatory
Warianty tytułu
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.
Wydawca
Rocznik
Strony
187--202
Opis fizyczny
Bibliogr. 21 poz., rys.
Twórcy
  • Department of Mathematics, Loyola College, Chennai 600034, India
  • Department of Mathematics, Loyola College, University of Madras, Chennai 600034, India
  • 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).
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-edd29075-64cb-4356-80e3-07ea0f3ca817
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.