Hostname: page-component-cd9895bd7-hc48f Total loading time: 0 Render date: 2024-12-27T08:02:01.124Z Has data issue: false hasContentIssue false
  • English
  • Français

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

Published online by Cambridge University Press:  15 April 2002

Imrich Vrťo
Imrich Vrťo*
Affiliation:
Institute of Mathematics, Slovak Academy of Sciences, P.O. Box 56, 84000 Bratislava, Slovak Republic.
Get access

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.

Keywords

Bisectioncutwidthinterconnection networksmesh of trees.
Type
Research Article
Information
RAIRO - Theoretical Informatics and Applications , Volume 34 , Issue 6 , November 2000 , pp. 515 - 519
Copyright
© EDP Sciences, 2000

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

D. Barth, Réseaux d'Interconnexion: Structures et Communications. PhD. Thesis. LABRI, Université Bordeaux I, France (1994).
Barth, D., 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. CrossRef
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.
F.T. Leighton, Complexity Issues in VLSI. MIT Press, Cambridge (1983).
F.T. Leighton, Introduction to Parallel Algorithms and Architectures: Arrays, Trees, and Hypercubes. Morgan Kaufmann Publishers, San Mateo (1992).
Lengauer, T., Upper and Lower Bounds for the Min Cut Linear Arrangenents Problem on Trees. SIAM J. Algebraic Discrete Methods 3 (1982) 99-113. CrossRef
Lopez, A.D. and Law, H.F.S., Dense Gate Matrix La, Ayout Method for MOS VLSI. IEEE Trans. Electr. Dev. 27 (1980) 1671-1675. CrossRef
Nakano, K., 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. CrossRef
Raspaud, A., Sýkora, O. and Vrto, I., Cutwidth of the de Bruijn Graph. RAIRO Theoret. Informatics Appl. 26 (1996) 509-514.
Yannakakis, M., Polynomial Al, Agorithm for the Min Cut Linear Arrangement of Trees. J. ACM 32 (1985) 950-988. CrossRef