Square-root rule of two-dimensional bandwidth problem

Lan Lin; Yixun Lin

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2011)

  • Volume: 45, Issue: 4, page 399-411
  • ISSN: 0988-3754

Abstract

top
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.

How to cite

top

Lin, Lan, and Lin, Yixun. "Square-root rule of two-dimensional bandwidth problem." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 45.4 (2011): 399-411. <http://eudml.org/doc/273000>.

@article{Lin2011,
abstract = {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.},
author = {Lin, Lan, Lin, Yixun},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {network layout; two-dimensional bandwidth; lower and upper bounds; optimal embedding; network communication; square root rule; bandwidth minimization problem},
language = {eng},
number = {4},
pages = {399-411},
publisher = {EDP-Sciences},
title = {Square-root rule of two-dimensional bandwidth problem},
url = {http://eudml.org/doc/273000},
volume = {45},
year = {2011},
}

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
PB - EDP-Sciences
VL - 45
IS - 4
SP - 399
EP - 411
AB - 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.
LA - eng
KW - network layout; two-dimensional bandwidth; lower and upper bounds; optimal embedding; network communication; square root rule; bandwidth minimization problem
UR - http://eudml.org/doc/273000
ER -

References

top
  1. [1] S.N. Bhatt and F.T. Leighton, A framework for solving VLSI graph layout problem. J. Comput. System Sci.28 (1984) 300–343. Zbl0543.68052MR760549
  2. [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. MR1684116
  3. [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. Zbl0953.68115MR1755405
  4. [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. Zbl0494.05057MR666794
  5. [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. Zbl0656.05058MR1205400
  6. [6] J. Diaz, J. Petit and M. Serna, A survey of graph layout problems. ACM Comput. Surv.34 (2002) 313–356. 
  7. [7] R. Hochberg, C. McDiarmid and M. Saks, On the bandwidth of triangulated triangles. Discrete Math.138 (1995) 261–265. Zbl0823.05048MR1322101
  8. [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. MR701766
  9. [9] L. Lin and Y. Lin, Two models of two-dimensional bandwidth problems, Inform. Process. Lett.110 (2010) 469–473. Zbl1229.68058MR2667148
  10. [10] J. Mai and H. Luo, Some theorems on the bandwidth of a graph. Acta Math. Appl. Sinica7 (1984) 86–95. Zbl0542.05052MR768053
  11. [11] P. Manuel, I. Rajasingh, B. Rajan and H. Mercy, Exact wirelength of hypercubes on a grid. Discrete Appl. Math.157 (2009) 1486–1495. Zbl1172.05330MR2510229
  12. [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. Zbl0949.05016MR1733674

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.