Header menu link for other important links
X
A tight bound for congestion of an embedding
P. Manuel, , R.S. Rajan, N. Parthiban, T.M. Rajalaxmi
Published in Springer Verlag
2015
Volume: 8959
   
Pages: 229 - 237
Abstract
Graph embedding has been known as a powerful tool for implementation of parallel algorithms or simulation of different interconnection networks. Congestion is one of the main optimization objectives in global routing. In this paper, we introduce a technique to obtain a tight bound for congestion of an embedding. Moreover, we give algorithms to compute exact congestion of embedding the hypercubes into the cylinder and the torus and prove that the bound obtained is sharp. © 2015, Springer International Publishing Switzerland.