Square-root rule of two-dimensional bandwidth problem∗

Lan Lin; Yixun Lin

RAIRO - Theoretical Informatics and Applications (2012)

  • 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 45.4 (2012): 399-411. <http://eudml.org/doc/222097>.

@article{Lin2012,
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},
keywords = {Network layout; two-dimensional bandwidth; lower and upper bounds; optimal embedding.; network layout; network communication; square root rule; bandwidth minimization problem; optimal embedding},
language = {eng},
month = {1},
number = {4},
pages = {399-411},
publisher = {EDP Sciences},
title = {Square-root rule of two-dimensional bandwidth problem∗},
url = {http://eudml.org/doc/222097},
volume = {45},
year = {2012},
}

TY - JOUR
AU - Lin, Lan
AU - Lin, Yixun
TI - Square-root rule of two-dimensional bandwidth problem∗
JO - RAIRO - Theoretical Informatics and Applications
DA - 2012/1//
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 layout; network communication; square root rule; bandwidth minimization problem; optimal embedding
UR - http://eudml.org/doc/222097
ER -

References

top
  1. S.N. Bhatt and F.T. Leighton, A framework for solving VLSI graph layout problem. J. Comput. System Sci.28 (1984) 300–343.  
  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.  
  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.  
  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.  
  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.  
  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.  
  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.  
  9. L. Lin and Y. Lin, Two models of two-dimensional bandwidth problems, Inform. Process. Lett.110 (2010) 469–473.  
  10. J. Mai and H. Luo, Some theorems on the bandwidth of a graph. Acta Math. Appl. Sinica7 (1984) 86–95.  
  11. P. Manuel, I. Rajasingh, B. Rajan and H. Mercy, Exact wirelength of hypercubes on a grid. Discrete Appl. Math.157 (2009) 1486–1495.  
  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.  

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.