no. 4
Square-root rule of two-dimensional bandwidth problem
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 45 (2011) no. 4, pp. 399-411

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.

DOI : 10.1051/ita/2011120
Classification : 05C78, 68R10
Keywords: network layout, two-dimensional bandwidth, lower and upper bounds, optimal embedding 
@article{ITA_2011__45_4_399_0,
     author = {Lin, Lan and Lin, Yixun},
     title = {Square-root rule of two-dimensional bandwidth problem},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {399--411},
     year = {2011},
     publisher = {EDP Sciences},
     volume = {45},
     number = {4},
     doi = {10.1051/ita/2011120},
     mrnumber = {2876114},
     zbl = {1235.05123},
     language = {en},
     url = {https://www.numdam.org/articles/10.1051/ita/2011120/}
}
TY  - JOUR
AU  - Lin, Lan
AU  - Lin, Yixun
TI  - Square-root rule of two-dimensional bandwidth problem
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2011
SP  - 399
EP  - 411
VL  - 45
IS  - 4
PB  - EDP Sciences
UR  - https://www.numdam.org/articles/10.1051/ita/2011120/
DO  - 10.1051/ita/2011120
LA  - en
ID  - ITA_2011__45_4_399_0
ER  - 
%0 Journal Article
%A Lin, Lan
%A Lin, Yixun
%T Square-root rule of two-dimensional bandwidth problem
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2011
%P 399-411
%V 45
%N 4
%I EDP Sciences
%U https://www.numdam.org/articles/10.1051/ita/2011120/
%R 10.1051/ita/2011120
%G en
%F ITA_2011__45_4_399_0
Lin, Lan; Lin, Yixun. Square-root rule of two-dimensional bandwidth problem. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 45 (2011) no. 4, pp. 399-411. doi: 10.1051/ita/2011120

[1] S.N. Bhatt and F.T. Leighton, A framework for solving VLSI graph layout problem. J. Comput. System Sci. 28 (1984) 300-343. | Zbl | MR

[2] S.L. Bezrukov, J.D. Chavez, L.H. Harper, M. Röttger and U.P. Schroeder, Embedding of hypercubes into grids, MFCS'98. Lect. Notes Comput. Sci. 1450 (1998) 693-701. | MR

[3] S.L. Bezrukov, J.D. Chavez, L.H. Harper, M. Röttger and U.P. Schroeder, The congestion of n-cube layout on a rectangular grid. Discrete Math. 213 (2000) 13-19. | Zbl | MR

[4] P.Z. Chinn, J. Chvátalová, A.K. Dewdney and N.E. Gibbs, The bandwidth problem for graphs and matrices - A survey. J. Graph Theor. 6 (1982) 223-254. | Zbl | MR

[5] 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. | Zbl | MR

[6] J. Diaz, J. Petit and M. Serna, A survey of graph layout problems. ACM Comput. Surv. 34 (2002) 313-356.

[7] R. Hochberg, C. Mcdiarmid and M. Saks, On the bandwidth of triangulated triangles. Discrete Math. 138 (1995) 261-265. | Zbl | MR

[8] Q. Li, M. Tao and Y. Shen, The bandwidth of torus grid graphs Cm × Cn. J. China Univ. Sci. Tech. 11 (1981) 1-16. | MR

[9] L. Lin and Y. Lin, Two models of two-dimensional bandwidth problems, Inform. Process. Lett. 110 (2010) 469-473. | Zbl | MR

[10] J. Mai and H. Luo, Some theorems on the bandwidth of a graph. Acta Math. Appl. Sinica 7 (1984) 86-95. | Zbl | MR

[11] P. Manuel, I. Rajasingh, B. Rajan and H. Mercy, Exact wirelength of hypercubes on a grid. Discrete Appl. Math. 157 (2009) 1486-1495. | Zbl | MR

[12] J. Opatrny and D. Sotteau, Embeddings of complete binary trees into grids and extended grids with total vertex-congestion 1. Discrete Appl. Math. 98 (2000) 237-254. | Zbl | MR

Cité par Sources :