Linear Wirelength of Folded Hypercubes

被引：30
作者：
Rajasingh I. [1 ]
Arockiaraj M. [1 ]
机构：
[1] Department of Mathematics, Loyola College
来源：
Mathematics in Computer Science | 2011年 / 5卷 / 1期
关键词：
Congestion; Edge isoperimetric problem; Embedding; Folded hypercube; Wirelength;
D O I：
10.1007/s11786-011-0085-2
中图分类号：
学科分类号：
摘要：
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⌊r/2⌋ × 2⌈r/2⌉ 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. © 2011 Springer Basel AG.
引用
收藏
页码：101 / 111
页数：10
相关论文
共 13 条
  • [1] Bezrukov S.L., Chavez J.D., Harper L.H., Rottger M., Schroeder U.P., Embedding of Hypercubes into Grids, MFCS, pp. 693-701, (1998)
  • [2] Bezrukov S.L., Monien B., Unger W., Wechsung G., Embedding ladders and caterpillars into the hypercube, Discret. Appl. Math., 83, pp. 21-29, (1998)
  • [3] Bezrukov S.L., Chavez J.D., Harper L.H., Rottger M., Schroeder U.P., The congestion of n-cube layout on a rectangular grid, Discret. Math., 213, pp. 13-19, (2000)
  • [4] Bezrukov S.L., Das S.K., Elsasser R., An edge-isoperimetric problem for powers of the Petersen graph, Ann. Comb., 4, pp. 153-169, (2000)
  • [5] Boals A.J., Gupta A.K., Sherwani N.A., A lower bound on embedding large hypercubes into small hypercubes, Congr. Numerentium, 78, pp. 141-151, (1990)
  • [6] Boals A.J., Gupta A.K., Sherwani N.A., Incomplete hypercubes: algorithms and embeddings, J. Supercomput., 8, pp. 263-294, (1994)
  • [7] Garey M.R., Johnson D.S., Computers and Intractability, A Guide to the Theory of NP-Completeness, (1979)
  • [8] Harper L.H., Global Methods for Combinatorial Isoperimetric Problems, (2004)
  • [9] 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, pp. 1171-1183, (1997)
  • [10] Katseff H., Incomplete hypercubes, IEEE Trans. Comput., 37, pp. 604-608, (1988)
12