{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T23:40:08Z","timestamp":1742600408535,"version":"3.40.2"},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540609223"},{"type":"electronic","value":"9783540497233"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1996]]},"DOI":"10.1007\/3-540-60922-9_14","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T21:03:35Z","timestamp":1330290215000},"page":"155-168","source":"Crossref","is-referenced-by-count":1,"title":["Embedding graphs with bounded treewidth into optimal hypercubes"],"prefix":"10.1007","author":[{"given":"Volker","family":"Heun","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ernst W.","family":"Mayr","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,7]]},"reference":[{"issue":"No.4","key":"14_CR1","doi-asserted-by":"crossref","first-page":"623","DOI":"10.1090\/S0002-9939-1986-0861764-9","volume":"98","author":"N. Alon","year":"1986","unstructured":"N. Alon, D. West: The Borsuk-Ulam Theorem and Bisection of Necklaces, Proc. of the Amer. Math. Soc., Vol. 98 (1986), No. 4, 623\u2013628.","journal-title":"Proc. of the Amer. Math. Soc."},{"issue":"No.2","key":"14_CR2","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1137\/0608024","volume":"8","author":"S. Arnborg","year":"1987","unstructured":"S. Arnborg, D. Corneil, A. Proskurowski: Complexity of Finding Embeddings in a k-tree, SIAM J. Alg. Disc. Meth., Vol. 8 (1987), No. 2, 277\u2013284.","journal-title":"SIAM J. Alg. Disc. Meth."},{"issue":"No.1","key":"14_CR3","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1137\/0221012","volume":"21","author":"S. Bhatt","year":"1992","unstructured":"S. Bhatt, F. Chung, T. Leighton, A. Rosenberg: Efficient Embeddings of Trees in Hypercubes, SIAM J. Comput., Vol. 21 (1992), No. 1, 151\u2013162.","journal-title":"SIAM J. Comput."},{"key":"14_CR4","doi-asserted-by":"crossref","unstructured":"H. Bodlaender, T. Hagerup: Parallel Algorithms with Optimal Speedup for Bounded Treewidth, Utrecht University, Technical Report UU-CS-1995-25, 1995.","DOI":"10.1007\/3-540-60084-1_80"},{"key":"14_CR5","doi-asserted-by":"crossref","unstructured":"M.Y. Chan: Embedding of d-Dimensional Grids into Optimal Hypercubes, Proceedings of the 1989 ACM Symposium on Parallel Algorithms and Architectures, 52\u201357.","DOI":"10.1145\/72935.72941"},{"issue":"No.5","key":"14_CR6","doi-asserted-by":"publisher","first-page":"834","DOI":"10.1137\/0220052","volume":"20","author":"M.Y. Chan","year":"1991","unstructured":"M.Y. Chan: Embedding of Grids into Optimal Hypercubes, SIAM J. Comput., Vol. 20 (1991), No. 5, 834\u2013864.","journal-title":"SIAM J. Comput."},{"key":"14_CR7","doi-asserted-by":"crossref","unstructured":"M.Y. Chan, F. Chin, C.N. Chu, W.K. Mak: Dilation-5 Embedding of 3-Dimensional Grids into Hypercubes Proceedings of the 5th IEEE Symposium on Parallel and Distributed Processing 1993, 285\u2013289.","DOI":"10.1109\/SPDP.1993.395521"},{"key":"14_CR8","doi-asserted-by":"crossref","unstructured":"R. Cypher, G. Plaxton: Deterministic Sorting in Nearly Logarithmic Time on the Hypercube and Related Computers, Proceedings of the 22nd Annual ACM Symposium on Theory of Computing 1990, 193\u2013203.","DOI":"10.1145\/100216.100240"},{"key":"14_CR9","doi-asserted-by":"crossref","first-page":"222","DOI":"10.1016\/0743-7315(91)90046-C","volume":"11","author":"K. Efe","year":"1991","unstructured":"K. Efe: Embedding Mesh of Trees in the Hypercube, J. Parallel and Ditsrib. Comput., Vol. 11 (1991), 222\u2013230.","journal-title":"J. Parallel and Ditsrib. Comput."},{"key":"14_CR10","unstructured":"T. Feder, E. Mayr: An Efficient Algorithm for Embedding Complete Binary Trees in the Hypercube, Stanford University, 1987."},{"key":"14_CR11","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1137\/0606010","volume":"6","author":"C. Goldberg","year":"1985","unstructured":"C. Goldberg, D. West: Bisection of Circle Colorings, SIAM J. Alg. Disc. Meth., 6 (1985), 93\u2013106.","journal-title":"SIAM J. Alg. Disc. Meth."},{"key":"14_CR12","doi-asserted-by":"crossref","first-page":"145","DOI":"10.21136\/CPM.1984.108506","volume":"109","author":"I. Havel","year":"1984","unstructured":"I. Havel: On Hamiltonian Circuits and Spanning Trees of Hypercubes, \u010casopis. P\u011bst. Mat., Vol. 109 (1984), 145\u2013152 [in Czech.].","journal-title":"\u010casopis. P\u011bst. Mat."},{"key":"14_CR13","doi-asserted-by":"crossref","first-page":"307","DOI":"10.21136\/CPM.1973.117800","volume":"98","author":"I. Havel","year":"1973","unstructured":"I. Havel, P. Liebl: Embedding the Polytomic Tree into the n-Cube, \u010casopis. P\u011bst. Mat., Vol. 98 (1973), 307\u2013314.","journal-title":"\u010casopis. P\u011bst. Mat."},{"key":"14_CR14","unstructured":"V. Heun, E.W. Mayr: A New Efficient Algorithm for Embedding an Arbitrary Binary Tree into Its Optimal Hypercube, Technical Report, TUM-I9321, Technische Universit\u00e4t M\u00fcnchen, 1993 (to appear in J. Algorithms)."},{"key":"14_CR15","doi-asserted-by":"crossref","unstructured":"T. Kloks: Treewidth: Computations and Approximations, Lecture Notes in Computer Science, Vol. 842, Springer-Verlag, 1994.","DOI":"10.1007\/BFb0045375"},{"issue":"No.4","key":"14_CR16","doi-asserted-by":"publisher","first-page":"639","DOI":"10.1137\/0221039","volume":"21","author":"T. Leighton","year":"1992","unstructured":"T. Leighton, M. Newman, A. Ranade, W. Schwabe: Dynamic Tree Embeddings in Butterflies and Hypercubes, SIAM J. Comput., Vol. 21 (1992), No. 4, 639\u2013654.","journal-title":"SIAM J. Comput."},{"key":"14_CR17","doi-asserted-by":"crossref","unstructured":"B. Monien, H. Sudborough: Simulating Binary Trees on Hypercubes, VLSI Algorithms and Architectures, Proceedings of the 3rd Aegean Workshop on Computing 1988, Lecture Notes in Computer Science, Vol. 319, Springer-Verlag, 170\u2013180.","DOI":"10.1007\/BFb0040385"},{"issue":"No.3","key":"14_CR18","doi-asserted-by":"publisher","first-page":"642","DOI":"10.1145\/322326.322329","volume":"29","author":"D. Nassimi","year":"1982","unstructured":"D. Nassimi, S. Sahni: Parallel Permutation and Sorting Algorithms and a New Generalized Connection Network, J. ACM, Vol. 29 (1982), No. 3, 642\u2013667.","journal-title":"J. ACM"},{"key":"14_CR19","unstructured":"Y. Saad, M. Schulz: Topological Properties of the Hypercube, Yale University Research Report, RR-389, 1985."},{"key":"14_CR20","doi-asserted-by":"publisher","first-page":"100","DOI":"10.1006\/jpdc.1995.1010","volume":"24","author":"X. Sheen","year":"1995","unstructured":"X. Sheen, Q. Hu, W. Liang: Embedding k-ary Complete Trees into Hypercubes, J. Parallel Distrib. Comput., Vol. 24 (1995), 100\u2013106.","journal-title":"J. Parallel Distrib. Comput."},{"key":"14_CR21","doi-asserted-by":"crossref","unstructured":"Q. Stout: Hypercubes and Pyramids, Proceedings of the NATO Advanced Research Workshop on Pyramidal Systems for Computer Vision 1986, Springer-verlag, Series F: Computers and System Science, 75\u201389.","DOI":"10.1007\/978-3-642-82940-6_5"}],"container-title":["Lecture Notes in Computer Science","STACS 96"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-60922-9_14.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T23:10:20Z","timestamp":1742598620000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-60922-9_14"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996]]},"ISBN":["9783540609223","9783540497233"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/3-540-60922-9_14","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1996]]}}}