Rajan, R Sundara

Kalinowski, Thomas

Klavzar, Sandi

Mokhtar, Hamid

Rajalaxmi, T M

2021-04

Interconnection networks provide an effective mechanism for exchanging data between processors in a parallel computing system. One of the most efficient interconnection networks is the hypercube due to its structural regularity, potential for parallel computation of various algorithms, and the high degree of fault tolerance. Thus it becomes the first choice of topological structure of parallel processing and computing systems. In this paper, lower bounds for the dilation, wirelength, and edge congestion of an embedding of a graph into a hypercube are proved. Two of these bounds are expressed in terms of the bisection width. Applying these results, the dilation and wirelength of embedding of certain complete multipartite graphs, folded hypercubes, wheels, and specific Cartesian products are computed.

Journal of Supercomputing, 77(4), p. 4135-4150

1573-0484

0920-8542

https://hdl.handle.net/1959.11/29593

Springer New York LLC

Lower bounds for dilation, wirelength, and edge congestion of embedding graphs into hypercubes

Journal Article

Publication