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 K2mn,2mn into grids M[2m × 2n], m ≤ n and cylinders P2m × C2n, 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: 09 Apr 2017 *

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