Optimal embedding of complete binary trees into lines and grids

1. M.J. Atallah, S.R. Kosaraju, ”Optimal simulations between mesh-connected arrays of processors”, Journal of the ACM, vol. 35 (1988), pp. 635–650.

   Google Scholar 

2. R. Aleliunas, A.L. Rosenberg, ”On Embedding Rectangular Grids in Square Grids”, IEEE Transactions on Computers, vol. C-31 (1982), pp. 907–913.

   Google Scholar 

3. P.Z. Chinn, J. Chvátalová, A.K. Dewedney, and N.E. Gibbs. The bandwidth problem for graphs and matrices — a survey. Journal of Graph Theory, 6:223–254, 1982.

   Google Scholar 

4. F.R.K. Chung, ”Labelings of Graphs”, in Selected Topics in Graph Theory III, edited by L.W. Beineke and R.J. Wilson, Academic Press, (1988) pp. 151–168.

   Google Scholar 

5. J.A. Ellis, ”Embedding Rectangular Grids into Square Grids”, Proceedings of the 3rd Aegean Workshop on Computing (AWOC): VLSI Algorithms and Architectures (1988), LNCS 319, pp. 181–190.

   Google Scholar 

6. M.J. Fischer, M.S. Paterson, ”Optimal Tree Layout”, Proceedings of the 12th ACM Symposium on the Theory of Computing (1980), pp. 177–189.

   Google Scholar 

7. M.R. Garey, D.S. Johnson, ”Computers and Intractability”, W.H. Freeman, New York, 1979.

   Google Scholar 

8. D. Gordon, ”Efficient Embeddings of Binary Trees in VLSI Arrays”, IEEE Transactions on Computers, vol. C-36 (1987), pp. 1009–1018.

   Google Scholar 

9. J. Haralambides, F. Makedon, B. Monien, ”Approximation Algorithms for the Bandwidth Minimization Problem for Caterpillar Graphs”, Proceedings of the 2nd IEEE Symposium on Parallel and Distributed Processing, (1990), pp. 301–307.

   Google Scholar 

10. B. Monien, ”The bandwidth minimization problem for caterpillars with hair length 3 is NP-complete”, SIAM J. Alg. and Discrete Methods, 7 (1986), pp. 505–512.

    Google Scholar 

11. B. Monien, ”Simulating Binary Trees on X-trees”, Proceedings of the 3rd A CM Symposium on Parallel Algorithms and Architectures (1991).

    Google Scholar 

12. B. Monien, I.H. Sudborough, ”Embedding one Interconnection Network in Another”, Computing Suppl. 7 (1990), pp. 257–282.

    Google Scholar 

13. mS. Paterson, W.L. Ruzzo, L. Snyder, ”Bounds on minimax edge length for complete binary trees”, Proceedings of the 13th ACM Symposium on the Theory of Computing (1981), pp. 293–299.

    Google Scholar 

14. A.L. Rosenberg, ”Graph embeddings 1988: Recent breakthroughs, new directions”, Proceedings of the 3rd Aegean Workshop on Computing (AWOC): VLSI Algorithms and Architectures (1988), LNCS 319, pp. 160–169.

    Google Scholar 

15. W.L. Ruzzo, L. Snyder, ”Minimum Edge Length Planar Embeddings of Trees”, in Kung, Sproull, Steele: VLSI Systems and Computations, Computer Science Press (1981), pp. 119–123.

    Google Scholar 

16. A.D. Singh, H.Y. Youn, ”Near Optimal Embedding of Binary Tree Architectures in VLSI”, Proceedings of the 8th International Conference on Distributed Computing Systems (1988), pp. 86–93.

    Google Scholar 

17. J.D. Ullman, ”Computational Aspects of VLSI”, Computer Science Press, 1984.

    Google Scholar 

18. P. Zienicke, ”Embedding of Treelike Graphs into 2-dimensional Meshes”, Proceedings of the 16th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 90).

    Google Scholar 

Download references