Header menu link for other important links
X
Embedding of hypercubes into generalized books
R.S. Rajan, , M. Arockiaraj, T.M. Rajalaxmi, B. Mahavir
Published in Charles Babbage Research Centre
2017
Volume: 135
   
Pages: 133 - 151
Abstract
Grapli embedding has been known as a powerful tool for implementation of parallel algorithms or simulation of different interconnection networks. An embedding f of a guest graph G into a host graph H is a bijection on the vertices such that each edge of G is mapped into a path of H. In this paper, we introduce a graph called the generalized book and the main results obtained are: (1) For r ≥ 3, the minimum wirelength of embedding r-dimensional hypercube Qr into the generalized book GB[2ri,2rj,2r3], where r1 + r2 + r3 = r. (2) A linear time algorithm to compute the exact wirelength of embedding hypercube into generalized book. (3) An algorithm for embedding hypercube into generalized book with dilation 3 proving that the lower bound obtained by Manuel et al. [28] is sharp.
About the journal
JournalArs Combinatoria
PublisherCharles Babbage Research Centre
ISSN03817032