Square-root rule of two-dimensional bandwidth problem
Lin, Lan ; Lin, Yixun
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 45 (2011), p. 399-411 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)

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.

Publié le : 2011-01-01
DOI : https://doi.org/10.1051/ita/2011120
Classification:  05C78,  68R10 
@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},
     volume = {45},
     year = {2011},
     pages = {399-411},
     doi = {10.1051/ita/2011120},
     mrnumber = {2876114},
     zbl = {1235.05123},
     language = {en},
     url = {http://dml.mathdoc.fr/item/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) pp. 399-411. doi : 10.1051/ita/2011120. http://gdmltest.u-ga.fr/item/ITA_2011__45_4_399_0/

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

[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 1684116

[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. | MR 1755405 | Zbl 0953.68115

[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. | MR 666794 | Zbl 0494.05057

[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. | MR 1205400 | Zbl 0656.05058

[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. | MR 1322101 | Zbl 0823.05048

[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 701766

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

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

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

[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. | MR 1733674 | Zbl 0949.05016