Paper Info
Title
On The Optimal Layout Of Balanced Complete Multipartite Graphs Into Grids And Tree Related Structures
Abstract
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. (C) 2020 Elsevier B.V. All rights reserved.
Year
DOI
Venue
2021
10.1016/j.dam.2020.08.022
DISCRETE APPLIED MATHEMATICS
Keywords
DocType
Volume
Complete t-partite graph, Embedding, Grid, Optimal layout
Journal
288
ISSN
Citations 
PageRank 
0166-218X
0
0.34
References 
Authors
0
4
Name
Order
Citations
PageRank
Micheal Arockiaraj1588.88
Jia-Bao Liu211021.86
J. Nancy Delaila300.68
Arul Jeya Shalini473.24