Cutwidth of the r-dimensional Mesh of d-ary Trees

Imrich Vrťo

RAIRO - Theoretical Informatics and Applications (2010)

  • Volume: 34, Issue: 6, page 515-519
  • ISSN: 0988-3754

Abstract

top
We prove that the cutwidth of the r-dimensional mesh of d-ary trees is of order Θ ( d ( r - 1 ) n + 1 ) , which improves and generalizes previous results.

How to cite

top

Vrťo, Imrich. "Cutwidth of the r-dimensional Mesh of d-ary Trees." RAIRO - Theoretical Informatics and Applications 34.6 (2010): 515-519. <http://eudml.org/doc/221959>.

@article{Vrťo2010,
abstract = { We prove that the cutwidth of the r-dimensional mesh of d-ary trees is of order $\Theta(d^\{(r-1)n+1\})$, which improves and generalizes previous results. },
author = {Vrťo, Imrich},
journal = {RAIRO - Theoretical Informatics and Applications},
keywords = {Bisection; cutwidth; interconnection networks; mesh of trees.; mesh; trees},
language = {eng},
month = {3},
number = {6},
pages = {515-519},
publisher = {EDP Sciences},
title = {Cutwidth of the r-dimensional Mesh of d-ary Trees},
url = {http://eudml.org/doc/221959},
volume = {34},
year = {2010},
}

TY - JOUR
AU - Vrťo, Imrich
TI - Cutwidth of the r-dimensional Mesh of d-ary Trees
JO - RAIRO - Theoretical Informatics and Applications
DA - 2010/3//
PB - EDP Sciences
VL - 34
IS - 6
SP - 515
EP - 519
AB - We prove that the cutwidth of the r-dimensional mesh of d-ary trees is of order $\Theta(d^{(r-1)n+1})$, which improves and generalizes previous results.
LA - eng
KW - Bisection; cutwidth; interconnection networks; mesh of trees.; mesh; trees
UR - http://eudml.org/doc/221959
ER -

References

top
  1. D. Barth, Réseaux d'Interconnexion: Structures et Communications. PhD. Thesis. LABRI, Université Bordeaux I, France (1994).  
  2. D. Barth, Bandwidth and cutwidth of the mesh of d-ary trees, in Proc. 2nd Intl. Euro-Par Conference, edited by L. Bougé et al. Springer Verlag, Berlin, Lecture Notes in Comput. Sci.1123 (1996) 243-246.  
  3. M.M. Eshagian and V.K. Prasanna, Parallel geometric algorithms for digital pictures on mesh of trees, in Proc. 27th Annual IEEE Symposium on Foundation of Computer Science. IEEE Computer Society Press, Los Alamitos (1986) 270-273.  
  4. F.T. Leighton, Complexity Issues in VLSI. MIT Press, Cambridge (1983).  
  5. F.T. Leighton, Introduction to Parallel Algorithms and Architectures: Arrays, Trees, and Hypercubes. Morgan Kaufmann Publishers, San Mateo (1992).  
  6. T. Lengauer, Upper and Lower Bounds for the Min Cut Linear Arrangenents Problem on Trees. SIAM J. Algebraic Discrete Methods3 (1982) 99-113.  
  7. A.D. Lopez and H.F.S. Law, A Dense Gate Matrix Layout Method for MOS VLSI. IEEE Trans. Electr. Dev.27 (1980) 1671-1675.  
  8. K. Nakano, Linear layout of generalized hypercubes, in Proc. 19th Intl. Workshop on Graph-Theoretic Concepts in Computer Science. Springer Verlag, Berlin, Lecture Notes in Comput. Sci.790 (1994) 364-375.  
  9. A. Raspaud, O. Sýkora and I. Vrto, Cutwidth of the de Bruijn Graph. RAIRO Theoret. Informatics Appl.26 (1996) 509-514.  
  10. M. Yannakakis, A Polynomial Algorithm for the Min Cut Linear Arrangement of Trees. J. ACM32 (1985) 950-988.  

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.