{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:16:18Z","timestamp":1725664578152},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540616269"},{"type":"electronic","value":"9783540706335"}],"license":[{"start":{"date-parts":[[1996,1,1]],"date-time":"1996-01-01T00:00:00Z","timestamp":820454400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1996]]},"DOI":"10.1007\/3-540-61626-8_29","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T22:05:22Z","timestamp":1330293922000},"page":"222-233","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A general method for efficient embeddings of graphs into optimal hypercubes"],"prefix":"10.1007","author":[{"given":"Volker","family":"Heun","sequence":"first","affiliation":[]},{"given":"Ernst W.","family":"Mayr","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,8]]},"reference":[{"key":"29_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. Am. Math. Soc., 98(1986), 623\u2013628.","journal-title":"Proc. Am. Math. Soc."},{"unstructured":"S. Bezrukov, B. Monien, W. Unger,G. Wechsung, Embedding Ladders and Caterpillars into the Hypercube, Preprint, GH-Univ. Paderborn, 1995, (to appear in Disc. Appl. Math.).","key":"29_CR2"},{"key":"29_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., 21(1992), 151\u2013162.","journal-title":"SIAM J. Comput."},{"unstructured":"S. Bhatt, I. Ipsen: How to Embed Trees in Hypercubes, Yale Univ., RR-443, 1985.","key":"29_CR4"},{"doi-asserted-by":"crossref","unstructured":"M. Chan: Embedding of d-Dimensional Grids into Optimal Hypercubes, Proc. of the 1989 Symp. on Parallel Algorithms and Architectures, 52\u201357.","key":"29_CR5","DOI":"10.1145\/72935.72941"},{"key":"29_CR6","doi-asserted-by":"publisher","first-page":"834","DOI":"10.1137\/0220052","volume":"20","author":"M. Chan","year":"1991","unstructured":"M. Chan: Embedding of Grids into Optimal Hypercubes, SIAM J. Comput, 20(1991), 834\u2013864.","journal-title":"SIAM J. Comput"},{"key":"29_CR7","doi-asserted-by":"publisher","first-page":"98","DOI":"10.1006\/jpdc.1996.0029","volume":"33","author":"M. Chan","year":"1996","unstructured":"M. Chan, F. Chin, C. Chu, W. Mak: Dilation-5 Embedding of 3-Dimensional Grids into Hypercubes, J. Parallel Distrib. Comput., 33(1996), 98\u2013106.","journal-title":"J. Parallel Distrib. Comput."},{"key":"29_CR8","doi-asserted-by":"publisher","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 Distrib. Comput., 11(1991), 222\u2013230.","journal-title":"J. Parallel Distrib. Comput."},{"key":"29_CR9","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":"29_CR10","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 (in Czech.), \u010casopis. P\u011bst. Mat., 109(1984), 145\u2013152.","journal-title":"\u010casopis. P\u011bst. Mat."},{"key":"29_CR11","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., 98(1973), 307\u2013314.","journal-title":"\u010casopis. P\u011bst. Mat."},{"key":"29_CR12","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1002\/jgt.3190100110","volume":"10","author":"I. Havel","year":"1986","unstructured":"I. Havel, P. Liebl: One-Legged Caterpillars Span Hypercubes, J. Graph Theory, 10(1986), 69\u201376.","journal-title":"J. Graph Theory"},{"key":"29_CR13","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1006\/jagm.1996.0018","volume":"20","author":"V. Heun","year":"1996","unstructured":"V. Heun, E. Mayr: A New Efficient Algorithm for Embedding an Arbitrary Binary Tree into Its Optimal Hypercube, J. Algorithms, 20(1996), 375\u2013199.","journal-title":"J. Algorithms"},{"unstructured":"V. Heun, E. Mayr: Embedding Graphs with Bounded Treewidth into Optimal Hypercubes, Proc. of the 13th Symp. on Theoretical Aspects of Computer Science, LNCS 1046, 157\u2013168.","key":"29_CR14"},{"unstructured":"V. Heun, E. Mayr: Optimal Dynamic Edge-Disjoint Embeddings of Complete Binary Trees into Hypercubes, (to appear in Proc. of the 4th Workshop on Parallel Systems and Algorithms).","key":"29_CR15"},{"unstructured":"V. Heun, E. Mayr: Efficient Dynamic Embeddings of Arbitrary Binary Trees into Hypercubes, (to appear in Proc. of the IRREGULAR'96).","key":"29_CR16"},{"key":"29_CR17","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., 21(1992), 639\u2013654.","journal-title":"SIAM J. Comput."},{"doi-asserted-by":"crossref","unstructured":"B. Monien, H. Sudborough: Simulating Binary Trees on Hypercubes, Proc. of the Aegean Workshop on Computing, LNCS 319, 170\u2013180.","key":"29_CR18","DOI":"10.1007\/BFb0040385"},{"key":"29_CR19","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1109\/TC.1981.6312172","volume":"C-30","author":"D. Nassimi","year":"1981","unstructured":"D. Nassimi, S. Sahni: Data Broadcasting in SIMD Computers, IEEE Trans. Comput., C-30(1981), 101\u2013107.","journal-title":"IEEE Trans. Comput."},{"unstructured":"Y. Saad, M. Schulz: Topological Properties of the Hypercube, Yale Univ., RR-389, 1985.","key":"29_CR20"},{"key":"29_CR21","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., 24(1995), 100\u2013106.","journal-title":"J. Parallel Distrib. Comput."},{"doi-asserted-by":"crossref","unstructured":"Q. Stout: Hypercubes and Pyramids, Proc. of the NATO Advanced Research Workshop on Pyramidal Systems for Computer Vision 1986, 75\u201389.","key":"29_CR22","DOI":"10.1007\/978-3-642-82940-6_5"},{"key":"29_CR23","doi-asserted-by":"publisher","first-page":"570","DOI":"10.1137\/0219038","volume":"19","author":"A. Wagner","year":"1990","unstructured":"A. Wagner, D. Corneil: Embedding Tree in a Hypercube is NP-Complete, SIAM J. Comput., 19(1990), 570\u2013590.","journal-title":"SIAM J. Comput."},{"key":"29_CR24","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1016\/0166-218X(93)90170-S","volume":"43","author":"A. Wagner","year":"1993","unstructured":"A. Wagner, D. Corneil: On the Complexity of the Embedding Problem for Hypercube Related Graphs, Discrete Appl. Math., 43(1993), 75\u201395.","journal-title":"Discrete Appl. Math."},{"key":"29_CR25","doi-asserted-by":"publisher","first-page":"238","DOI":"10.1016\/0743-7315(85)90026-7","volume":"2","author":"A. Wu","year":"1985","unstructured":"A. Wu: Embedding of Tree Networks into Hypercubes, J. Parallel Distrib. Comput., 2(1985) 238\u2013249.","journal-title":"J. Parallel Distrib. Comput."}],"container-title":["Lecture Notes in Computer Science","Euro-Par'96 Parallel Processing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-61626-8_29","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,12,31]],"date-time":"2021-12-31T10:50:59Z","timestamp":1640947859000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-61626-8_29"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996]]},"ISBN":["9783540616269","9783540706335"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/3-540-61626-8_29","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1996]]},"assertion":[{"value":"8 June 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}