Abstract
Manuel et al. (Discret. Appl. Math. 157(7):1486–1495, 2009) obtained the exact wirelength of an r-dimensional hypercube into a path as well as a \({2^{\lfloor r/2\rfloor}\times 2^{\lceil r/2\rceil}}\) grid and conjectured the same for a folded hypercube. In this paper we solve the edge isoperimetric problem for folded hypercubes and thereby obtain the exact wirelength of folded hypercubes into paths. Further we compute the exact wirelength of the r-dimensional folded hypercubes into 2k × 2r−k grids.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Bezrukov, S.L., Chavez, J.D., Harper, L.H., Röttger, M., Schroeder, U.P.: Embedding of Hypercubes into Grids. In: MFCS, pp. 693–701 (1998)
Bezrukov S.L., Monien B., Unger W., Wechsung G.: Embedding ladders and caterpillars into the hypercube. Discret. Appl. Math. 83, 21–29 (1998)
Bezrukov S.L., Chavez J.D., Harper L.H., Röttger M., Schroeder U.P.: The congestion of n-cube layout on a rectangular grid. Discret. Math. 213, 13–19 (2000)
Bezrukov S.L., Das S.K., Elsässer R.: An edge-isoperimetric problem for powers of the Petersen graph. Ann. Comb. 4, 153–169 (2000)
Boals A.J., Gupta A.K., Sherwani N.A.: A lower bound on embedding large hypercubes into small hypercubes. Congr. Numerentium 78, 141–151 (1990)
Boals A.J., Gupta A.K., Sherwani N.A.: Incomplete hypercubes: algorithms and embeddings. J. Supercomput. 8, 263–294 (1994)
Garey M.R., Johnson D.S.: Computers and Intractability, A Guide to the Theory of NP-Completeness. Freeman, San Francisco (1979)
Harper L.H.: Global Methods for Combinatorial Isoperimetric Problems. Cambridge University Press, London (2004)
Chen H.-L., Tzeng N.-F.: A Boolean expression-based approach for maximum incomplete subcube identification in faulty hypercubes. IEEE Trans. Parallel Distrib. Syst. 8, 1171–1183 (1997)
Katseff H.: Incomplete hypercubes. IEEE Trans. Comput. 37, 604–608 (1988)
Manuel P., Rajasingh I., Rajan B., Mercy H.: Exact wirelength of hypercube on a grid. Discret. Appl. Math. 157(7), 1486–1495 (2009)
Xu J.-M.: Topological Structure and Analysis of Interconnection Networks. Kluwer Academic Publishers, Dordrecht (2001)
Zhu Q., Xu J.-M., Hou X., Xu M.: On reliability of the folded hypercubes. Inf. Sci. 177, 1782–1788 (2007)
Author information
Authors and Affiliations
Corresponding author
Additional information
This work is supported by the Department of Science and Technology, Government of India, Project No. SR/S4/MS: 494/07.
Rights and permissions
About this article
Cite this article
Rajasingh, I., Arockiaraj, M. Linear Wirelength of Folded Hypercubes. Math.Comput.Sci. 5, 101–111 (2011). https://doi.org/10.1007/s11786-011-0085-2
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11786-011-0085-2