Abstract
In this paper we show that the cutwidth of the mesh of d-ary trees MT(d, n) is of order θ(d n+1), which improves both upper and lower bounds of Barth [2], by a factor of d.
This research was supported by Grant No. 95/5305/277 of Slovak Grant Agency.
Chapter PDF
References
Barth, D., Réseaux d'interconnexion: structures et communications, PhD. Thesis, LABRI, Université Bordeaux I, 1994.
Barth, D., Bandwidth and cutwidth of the mesh of d-ary trees, in: Proc. 2nd Intl. Euro-Par Conference, Lecture Notes in Computer Science 1123, Springer Verlag, Berlin, 1996, 243–246.
Eshagian, M.M., Prasanna, V.K., 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.
Leighton, F. T., 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 and Discrete Methods 3 (1982), 99–113.
Lopez, A.D., Law, H.F.S., A dense gate matrix layout method for MOS VLSI, IEEE Transactions on Electronic Devices 27 (1980), 1671–1675.
Nakano, K., Linear layout of generalized hypercubes, in: Proc. 19th Intl. Workshop on Graph-Theoretic Concepts in Computer Science, Lecture Notes in Computer Science 790, Springer Verlag, Berlin, 1994, 364–375.
Raspaud, A., Sýkora, 0., Vrt'o, I., Cutwidth of the de Bruiju graph, RAIRO-Theoretical Informatics and Applications 26 (1996), 509–514.
Yannakakis, M., A polynomial algorithm for the Min cut linear arrangement of trees, J. ACM 32 (1985), 950–988.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1997 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Vrt'o, I. (1997). Cutwidth of the mesh of d-ary trees. In: Lengauer, C., Griebl, M., Gorlatch, S. (eds) Euro-Par'97 Parallel Processing. Euro-Par 1997. Lecture Notes in Computer Science, vol 1300. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0002739
Download citation
DOI: https://doi.org/10.1007/BFb0002739
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-63440-9
Online ISBN: 978-3-540-69549-3
eBook Packages: Springer Book Archive