{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:00:24Z","timestamp":1725663624629},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540551218"},{"type":"electronic","value":"9783540467359"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1992]]},"DOI":"10.1007\/3-540-55121-2_3","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T04:48:19Z","timestamp":1330231699000},"page":"25-35","source":"Crossref","is-referenced-by-count":13,"title":["Optimal embedding of complete binary trees into lines and grids"],"prefix":"10.1007","author":[{"given":"R.","family":"Heckmann","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"R.","family":"Klasing","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"B.","family":"Monien","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"W.","family":"Unger","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,5]]},"reference":[{"key":"3_CR1","doi-asserted-by":"crossref","first-page":"635","DOI":"10.1145\/44483.44494","volume":"35","author":"M.J. Atallah","year":"1988","unstructured":"M.J. Atallah, S.R. Kosaraju, \u201dOptimal simulations between mesh-connected arrays of processors\u201d, Journal of the ACM, vol. 35 (1988), pp. 635\u2013650.","journal-title":"Journal of the ACM"},{"key":"3_CR2","doi-asserted-by":"crossref","first-page":"907","DOI":"10.1109\/TC.1982.1676109","volume":"C-31","author":"R. Aleliunas","year":"1982","unstructured":"R. Aleliunas, A.L. Rosenberg, \u201dOn Embedding Rectangular Grids in Square Grids\u201d, IEEE Transactions on Computers, vol. C-31 (1982), pp. 907\u2013913.","journal-title":"IEEE Transactions on Computers"},{"key":"3_CR3","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1002\/jgt.3190060302","volume":"6","author":"P.Z. Chinn","year":"1982","unstructured":"P.Z. Chinn, J. Chv\u00e1talov\u00e1, A.K. Dewedney, and N.E. Gibbs. The bandwidth problem for graphs and matrices \u2014 a survey. Journal of Graph Theory, 6:223\u2013254, 1982.","journal-title":"Journal of Graph Theory"},{"key":"3_CR4","unstructured":"F.R.K. Chung, \u201dLabelings of Graphs\u201d, in Selected Topics in Graph Theory III, edited by L.W. Beineke and R.J. Wilson, Academic Press, (1988) pp. 151\u2013168."},{"key":"3_CR5","doi-asserted-by":"crossref","unstructured":"J.A. Ellis, \u201dEmbedding Rectangular Grids into Square Grids\u201d, Proceedings of the 3rd Aegean Workshop on Computing (AWOC): VLSI Algorithms and Architectures (1988), LNCS 319, pp. 181\u2013190.","DOI":"10.1007\/BFb0040386"},{"key":"3_CR6","unstructured":"M.J. Fischer, M.S. Paterson, \u201dOptimal Tree Layout\u201d, Proceedings of the 12th ACM Symposium on the Theory of Computing (1980), pp. 177\u2013189."},{"key":"3_CR7","volume-title":"Computers and Intractability","author":"M.R. Garey","year":"1979","unstructured":"M.R. Garey, D.S. Johnson, \u201dComputers and Intractability\u201d, W.H. Freeman, New York, 1979."},{"key":"3_CR8","doi-asserted-by":"crossref","first-page":"1009","DOI":"10.1109\/TC.1987.5009532","volume":"C-36","author":"D. Gordon","year":"1987","unstructured":"D. Gordon, \u201dEfficient Embeddings of Binary Trees in VLSI Arrays\u201d, IEEE Transactions on Computers, vol. C-36 (1987), pp. 1009\u20131018.","journal-title":"IEEE Transactions on Computers"},{"key":"3_CR9","doi-asserted-by":"crossref","unstructured":"J. Haralambides, F. Makedon, B. Monien, \u201dApproximation Algorithms for the Bandwidth Minimization Problem for Caterpillar Graphs\u201d, Proceedings of the 2nd IEEE Symposium on Parallel and Distributed Processing, (1990), pp. 301\u2013307.","DOI":"10.1109\/SPDP.1990.143552"},{"key":"3_CR10","doi-asserted-by":"crossref","first-page":"505","DOI":"10.1137\/0607057","volume":"7","author":"B. Monien","year":"1986","unstructured":"B. Monien, \u201dThe bandwidth minimization problem for caterpillars with hair length 3 is NP-complete\u201d, SIAM J. Alg. and Discrete Methods, 7 (1986), pp. 505\u2013512.","journal-title":"SIAM J. Alg. and Discrete Methods"},{"key":"3_CR11","doi-asserted-by":"crossref","unstructured":"B. Monien, \u201dSimulating Binary Trees on X-trees\u201d, Proceedings of the 3rd A CM Symposium on Parallel Algorithms and Architectures (1991).","DOI":"10.1145\/113379.113393"},{"key":"3_CR12","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1007\/978-3-7091-9076-0_13","volume":"7","author":"B. Monien","year":"1990","unstructured":"B. Monien, I.H. Sudborough, \u201dEmbedding one Interconnection Network in Another\u201d, Computing Suppl. 7 (1990), pp. 257\u2013282.","journal-title":"Computing Suppl."},{"key":"3_CR13","unstructured":"mS. Paterson, W.L. Ruzzo, L. Snyder, \u201dBounds on minimax edge length for complete binary trees\u201d, Proceedings of the 13th ACM Symposium on the Theory of Computing (1981), pp. 293\u2013299."},{"key":"3_CR14","unstructured":"A.L. Rosenberg, \u201dGraph embeddings 1988: Recent breakthroughs, new directions\u201d, Proceedings of the 3rd Aegean Workshop on Computing (AWOC): VLSI Algorithms and Architectures (1988), LNCS 319, pp. 160\u2013169."},{"key":"3_CR15","unstructured":"W.L. Ruzzo, L. Snyder, \u201dMinimum Edge Length Planar Embeddings of Trees\u201d, in Kung, Sproull, Steele: VLSI Systems and Computations, Computer Science Press (1981), pp. 119\u2013123."},{"key":"3_CR16","unstructured":"A.D. Singh, H.Y. Youn, \u201dNear Optimal Embedding of Binary Tree Architectures in VLSI\u201d, Proceedings of the 8th International Conference on Distributed Computing Systems (1988), pp. 86\u201393."},{"key":"3_CR17","unstructured":"J.D. Ullman, \u201dComputational Aspects of VLSI\u201d, Computer Science Press, 1984."},{"key":"3_CR18","doi-asserted-by":"crossref","unstructured":"P. Zienicke, \u201dEmbedding of Treelike Graphs into 2-dimensional Meshes\u201d, Proceedings of the 16th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 90).","DOI":"10.1007\/3-540-53832-1_42"}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-55121-2_3.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T15:57:40Z","timestamp":1605628660000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-55121-2_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1992]]},"ISBN":["9783540551218","9783540467359"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/3-540-55121-2_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1992]]}}}