Article contents
Cutwidth of the r-dimensional Mesh of d-ary Trees
Published online by Cambridge University Press: 15 April 2002
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.
- Type
- Research Article
- Information
- RAIRO - Theoretical Informatics and Applications , Volume 34 , Issue 6 , November 2000 , pp. 515 - 519
- Copyright
- © EDP Sciences, 2000
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
- 7
- Cited by