A linear time algorithm for embedding hypercube into cylinder and torus

详细信息    查看全文

• 作者：Sundara Rajan R.^a ; ¹ ; ^{vprsundar@gmail.com" class="auth_mail} ; Indra Rajasingh^a ; Parthiban N.^b ; Rajalaxmi T.M.^c
• 关键词：Embedding ; Wirelength ; Hypercube ; Cylinder ; Torus
• 刊名：Theoretical Computer Science
• 出版年：3 July 2014
• 年：2014
• 卷：542
• 期：Complete
• 页码：108-115
• 全文大小：317 K

文摘

In this paper we solve two conjectures proposed by Manuel et al. (2011) [7] to obtain exact wirelength of embedding an r  -dimensional hypercube into cylinder C_2^r1×P_2^r2$C_{2^{r_1}}\times P_{2^{r_2}}$ and torus C_2^r1×C_2^r2$C_{2^{r_1}}\times C_{2^{r_2}}$, where r₁+r₂=r$r_1+r_2=r$ and r₁≤r₂$r_1\le r_2$. We provide a linear time algorithm to compute the exact wirelength of embedding hypercube into cylinder and torus. Further we extend the result for higher dimensional cylinder and torus.