Hostname: page-component-74656f9884-2dmjx Total loading time: 0 Render date: 2026-11-09T21:20:53.215Z Has data issue: false hasContentIssue false
  • English
  • Français

Square-root rule of two-dimensional bandwidth problem∗

Published online by Cambridge University Press:  22 September 2011

Lan Lin  and
Yixun Lin
Lan Lin
Affiliation:
School of Electronics and Information Engineering, Tongji University, Shanghai 200092, P.R. China The Key Laboratory of Cognitive Radio and Information Processing, Ministry of Education, Guilin University of Electronic Technology, Guilin 541004, P.R. China
Yixun Lin
Affiliation:
Department of Mathematics, Zhengzhou University, Zhengzhou 450052, P.R. China. linyixun@zzu.edu.cn

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

The bandwidth minimization problem is of significance in network communication and related areas. Let G be a graph of n vertices. The two-dimensional bandwidth B2(G) of G is the minimum value of the maximum distance between adjacent vertices when G is embedded into an n × n grid in the plane. As a discrete optimization problem, determining B2(G) is NP-hard in general. However, exact results for this parameter can be derived for some special classes of graphs. This paper studies the “square-root rule” of the two-dimensional bandwidth, which is useful in evaluating B2(G) for some typical graphs.

Keywords

Network layouttwo-dimensional bandwidthlower and upper boundsoptimal embedding.

Information

Type
Research Article
Information
RAIRO - Theoretical Informatics and Applications , Volume 45 , Issue 4 , November 2011 , pp. 399 - 411
Copyright
© EDP Sciences 2011

References

Références

Bhatt, S.N. and Leighton, F.T., A framework for solving VLSI graph layout problem. J. Comput. System Sci. 28 (1984) 300–343. Google Scholar
Bezrukov, S.L., Chavez, J.D., Harper, L.H., Röttger, M. and Schroeder, U.P., Embedding of hypercubes into grids, MFCS’98. Lect. Notes Comput. Sci. 1450 (1998) 693–701. Google Scholar
Bezrukov, S.L., Chavez, J.D., Harper, L.H., Röttger, M. and Schroeder, U.P., The congestion of n-cube layout on a rectangular grid. Discrete Math. 213 (2000) 13–19. Google Scholar
Chinn, P.Z., Chvátalová, J., Dewdney, A.K. and Gibbs, N.E., The bandwidth problem for graphs and matrices – A survey. J. Graph Theor. 6 (1982) 223–254. Google Scholar
F.R.K. Chung, Labelings of graphs, in Selected topics in graph theory, L.W. Beineke and R.J. Wilson, Eds. 3 (1988) 151–168.
Diaz, J., Petit, J. and Serna, M., A survey of graph layout problems. ACM Comput. Surv. 34 (2002) 313–356. Google Scholar
Hochberg, R., McDiarmid, C. and Saks, M., On the bandwidth of triangulated triangles. Discrete Math. 138 (1995) 261–265. Google Scholar
Li, Q., Tao, M. and Shen, Y., The bandwidth of torus grid graphs C m × C n. J. China Univ. Sci. Tech. 11 (1981) 1–16. Google Scholar
Lin, L. and Lin, Y., Two models of two-dimensional bandwidth problems, Inform. Process. Lett. 110 (2010) 469–473. Google Scholar
Mai, J. and Luo, H., Some theorems on the bandwidth of a graph. Acta Math. Appl. Sinica 7 (1984) 86–95. Google Scholar
Manuel, P., Rajasingh, I., Rajan, B. and Mercy, H., Exact wirelength of hypercubes on a grid. Discrete Appl. Math. 157 (2009) 1486–1495. Google Scholar
Opatrny, J. and Sotteau, D., Embeddings of complete binary trees into grids and extended grids with total vertex-congestion 1. Discrete Appl. Math. 98 (2000) 237–254. Google Scholar