Embedding complete multi-partite graphs into Cartesian product of paths and cycles

2019/01/23 by R. Sundara Rajan, Rajan, R. Sundara, A. Arul Shantrinal +9
Computer Science · Engineering · #05C60 #05C85 #Advanced Graph Theory Research #Advanced Optical Network Technologies #Combinatorics (math.CO) #FOS: Mathematics #Interconnection Networks and Systems

paper · pdf · doi:10.48550/arxiv.1901.07717

openalex publication_date 2019/01/23 · openalex created_date 2019/02/21 · openalex updated_date 2026/07/28

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 cycles, which include n-cube, n-dimensional mesh (grid), n-dimensional cylinder and n-dimensional torus, etc., as the subfamilies.

Related

• Embedding hypercubes into torus and Cartesian product of paths and cycles for minimizing wirelength
• Embedding onto Wheel-like Networks
• Embedding Complete Multipartite Graphs into Certain Trees
• Embedding into Special Classes of Cyclic Graphs and its Applications in VLSI Layout
• Maximising the number of regions when embedding a N-cycle graph