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.
Mots-clés : 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},
publisher = {EDP-Sciences},
volume = {45},
number = {4},
year = {2011},
doi = {10.1051/ita/2011120},
mrnumber = {2876114},
zbl = {1235.05123},
language = {en},
url = {http://archive.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 - http://archive.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 http://archive.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. http://archive.numdam.org/articles/10.1051/ita/2011120/
[1] and , A framework for solving VLSI graph layout problem. J. Comput. System Sci. 28 (1984) 300-343. | MR | Zbl
[2] , , , and , Embedding of hypercubes into grids, MFCS'98. Lect. Notes Comput. Sci. 1450 (1998) 693-701. | MR
[3] , , , and , The congestion of n-cube layout on a rectangular grid. Discrete Math. 213 (2000) 13-19. | MR | Zbl
[4] , , and , The bandwidth problem for graphs and matrices - A survey. J. Graph Theor. 6 (1982) 223-254. | MR | Zbl
[5] , Labelings of graphs, in Selected topics in graph theory, L.W. Beineke and R.J. Wilson, Eds. 3 (1988) 151-168. | MR | Zbl
[6] , and , A survey of graph layout problems. ACM Comput. Surv. 34 (2002) 313-356.
[7] , and , On the bandwidth of triangulated triangles. Discrete Math. 138 (1995) 261-265. | MR | Zbl
[8] , and , The bandwidth of torus grid graphs Cm × Cn. J. China Univ. Sci. Tech. 11 (1981) 1-16. | MR
[9] and , Two models of two-dimensional bandwidth problems, Inform. Process. Lett. 110 (2010) 469-473. | MR | Zbl
[10] and , Some theorems on the bandwidth of a graph. Acta Math. Appl. Sinica 7 (1984) 86-95. | MR | Zbl
[11] , , and , Exact wirelength of hypercubes on a grid. Discrete Appl. Math. 157 (2009) 1486-1495. | MR | Zbl
[12] and , Embeddings of complete binary trees into grids and extended grids with total vertex-congestion 1. Discrete Appl. Math. 98 (2000) 237-254. | MR | Zbl
Cité par Sources :
