Please use this identifier to cite or link to this item:
Scopus Web of Science® Altmetric
Type: Journal article
Title: Embedding meshes and tori on double-loop networks of the same size
Author: Chen, Y.
Shen, H.
Citation: IEEE Transactions on Computers, 2011; 60(8):1157-1168
Publisher: IEEE Computer Soc
Issue Date: 2011
ISSN: 0018-9340
Statement of
Yawen Chen and Hong Shen
Abstract: Double-loop networks are extensions of ring networks and are widely used in the design and implementation of local area networks and parallel processing architectures. However, embedding of other types of networks on double-loop networks has not been well studied due to the topological complexity of double-loop networks. The traditional L-shape, designed to compute the diameter of double-loop networks, is not effective to solve the embedding problem. We propose a novel tessellation approach to partition the geometric plane of double-loop networks into a set of parallelogram tiles, called P-shape. Based on the characteristics of P-shape, we design a simple embedding scheme, namely, P-shape embedding, that embeds meshes and tori on double-loop networks in a systematic way. Under P-shape embedding, we evaluate the embedding metrics of dilation, average dilation, and congestion, which depend heavily on the parameters of P-shape. A main merit of P-shape embedding is that a large fraction of embedded mesh/torus edges have edge dilation 1, resulting in a low average dilation. These are the first results, to our knowledge, for embedding meshes and tori on double-loop networks which is of great significance due to the popularity of these architectures. Our P-shape construction bridges between regular graphs and double-loop networks, and provides a powerful tool for studying double-loop networks.
Keywords: Double-loop networks; mesh; torus; graph embedding; dilation.
Rights: © 2011 IEEE
RMID: 0020110472
DOI: 10.1109/TC.2010.275
Grant ID:
Appears in Collections:Computer Science publications

Files in This Item:
File Description SizeFormat 
RA_hdl_69825.pdfRestricted Access1.05 MBAdobe PDFView/Open

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.