Title: Embedding complete bipartite graph into grid with optimum congestion and wirelength

Authors: A. Berin Greeni; Indra Rajasingh

Addresses: School of Advanced Sciences, VIT University, Chennai, India ' School of Advanced Sciences, VIT University, Chennai, India

Abstract: Interconnection networks provide an effective mechanism for exchanging data between processors in a parallel computing system. Graph embedding problems have gained importance in the field of interconnection networks. In this paper, we determine the congestion and wirelength of embedding complete bipartite graphs K_2mn,2mn into grids M[2m × 2n], m ≤ n and cylinders P_2m × C_2n, m ≤ n.

Keywords: embedding; congestion; edge isoperimetric problem; complete bipartite graph; grid; cylinder.

DOI: 10.1504/IJNVO.2017.083544

International Journal of Networking and Virtual Organisations, 2017 Vol.17 No.1, pp.64 - 75

Received: 11 Aug 2015
Accepted: 22 Feb 2016
Published online: 10 Apr 2017 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article