{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:21:29Z","timestamp":1725664889983},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540625599"},{"type":"electronic","value":"9783540680727"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1997]]},"DOI":"10.1007\/3-540-62559-3_12","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T22:40:13Z","timestamp":1330296013000},"page":"126-140","source":"Crossref","is-referenced-by-count":0,"title":["More general parallel tree contraction: Register allocation and broadcasting in a tree"],"prefix":"10.1007","author":[{"given":"Krzysztof","family":"Diks","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hagerup","family":"Torben","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,3]]},"reference":[{"key":"12_CR1","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1016\/0196-6774(89)90017-5","volume":"10","author":"K. Abrahamson","year":"1989","unstructured":"K. Abrahamson, N. Dadoun, D. G. Kirkpatrick, and T. Przytycka, A simple parallel tree contraction algorithm, J. Algorithms\n10 (1989), pp. 287\u2013302.","journal-title":"J. Algorithms"},{"key":"12_CR2","volume-title":"Compilers: Principles, Techniques, and Tools","author":"A. V. Aho","year":"1986","unstructured":"A. V. Aho, R. Sethi, and J. D. Ullman, Compilers: Principles, Techniques, and Tools, Addison-Wesley, Reading, MA, 1986."},{"key":"12_CR3","doi-asserted-by":"crossref","unstructured":"M. Ajtai, J. Koml\u00f3s, and E. Szemer\u00e9di, An O(n log n) sorting network, In Proc. 15th Annual ACM Symposium on Theory of Computing (STOC 1983), pp. 1\u20139.","DOI":"10.1145\/800061.808726"},{"key":"12_CR4","doi-asserted-by":"crossref","first-page":"266","DOI":"10.1006\/inco.1993.1056","volume":"106","author":"O. Berkman","year":"1993","unstructured":"O. Berkman and U. Vishkin, On parallel integer merging, Inform. and Comput.\n106 (1993), pp. 266\u2013285.","journal-title":"Inform. and Comput."},{"key":"12_CR5","doi-asserted-by":"crossref","first-page":"206","DOI":"10.1007\/3-540-59071-4_49","volume":"903","author":"S. Chaudhuri","year":"1994","unstructured":"S. Chaudhuri and T. Hagerup, Prefix graphs and their applications, In Proc. 20th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 1994), Springer Lecture Notes in Computer Science, Vol. 903, pp. 206\u2013218.","journal-title":"Springer Lecture Notes in Computer Science"},{"key":"12_CR6","doi-asserted-by":"crossref","first-page":"770","DOI":"10.1137\/0217049","volume":"17","author":"R. Cole","year":"1988","unstructured":"R. Cole, Parallel merge sort, SIAM J. Comput.\n17 (1988), pp. 770\u2013785.","journal-title":"SIAM J. Comput."},{"key":"12_CR7","doi-asserted-by":"crossref","first-page":"32","DOI":"10.1016\/S0019-9958(86)80023-7","volume":"70","author":"R. Cole","year":"1986","unstructured":"R. Cole and U. Vishkin, Deterministic coin tossing with applications to optimal parallel list ranking, Inform. and Control\n70 (1986), pp. 32\u201353.","journal-title":"Inform. and Control"},{"key":"12_CR8","doi-asserted-by":"crossref","first-page":"606","DOI":"10.1137\/0217037","volume":"17","author":"F. E. Fich","year":"1988","unstructured":"F. E. Fich, P. Ragde, and A. Wigderson, Relations between concurrent-write models of parallel computation, SIAM J. Comput.\n17 (1988), pp. 606\u2013627.","journal-title":"SIAM J. Comput."},{"key":"12_CR9","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1007\/978-1-4684-5511-3_9","volume-title":"Concurrent Computations: Algorithms, Architecture, and Technology","author":"H. Gazit","year":"1988","unstructured":"H. Gazit, G. L. Miller, and S.-H. Teng, Optimal tree contraction in the EREW model, In Concurrent Computations: Algorithms, Architecture, and Technology, S. K. Tewksbury, B. W. Dickinson, and S. C. Schwartz (eds.), Chap. 9, pp. 139\u2013156, Plenum Press, New York, 1988."},{"key":"12_CR10","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1007\/BFb0040378","volume":"319","author":"S. R. Kosaraju","year":"1988","unstructured":"S. R. Kosaraju and A. L. Delcher, Optimal parallel evaluation of tree-structured computations by raking, In Proc. 3rd Aegean Workshop on Computing (AWOC 1988), Springer Lecture Notes in Computer Science, Vol. 319, pp. 101\u2013110.","journal-title":"Springer Lecture Notes in Computer Science"},{"key":"12_CR11","doi-asserted-by":"crossref","unstructured":"G. L. Miller and J. H. Reif, Parallel tree contraction and its application, In Proc. 26th Annual Symposium on Foundations of Computer Science (FOCS 1985), pp. 478\u2013489.","DOI":"10.1109\/SFCS.1985.43"},{"key":"12_CR12","series-title":"Advances in Computing Research, Vol. 5","first-page":"47","volume-title":"Randomness and Computation","author":"G. L. Miller","year":"1989","unstructured":"G. L. Miller and J. H. Reif, Parallel tree contraction, Part 1: Fundamentals, preprint, 1987. The final version (not available to us) appeared in Randomness and Computation, Advances in Computing Research, Vol. 5, S. Micali (ed.), pp. 47\u201372, JAI Press, Greenwich, CT, 1989."},{"key":"12_CR13","doi-asserted-by":"crossref","first-page":"1128","DOI":"10.1137\/0220070","volume":"20","author":"G. L. Miller","year":"1991","unstructured":"G. L. Miller and J. H. Reif, Parallel tree contraction, Part 2: Further applications, SIAM J. Comput.\n20 (1991), pp. 1128\u20131147.","journal-title":"SIAM J. Comput."},{"key":"12_CR14","unstructured":"G. L. Miller and S.-H. Teng, Tree-based parallel algorithm design, manuscript. A preliminary version appeared in Proc. 2nd International Conference on Supercomputing (1987), pp. 392\u2013403."},{"key":"12_CR15","first-page":"115","volume-title":"Synthesis of Parallel Algorithms","author":"M. Reid-Miller","year":"1993","unstructured":"M. Reid-Miller, G. L. Miller, and F. Modugno, List ranking and parallel tree contraction, In Synthesis of Parallel Algorithms, J.H. Reif (ed.), Chap. 3, pp. 115\u2013194, Morgan Kaufmann Publ., San Mateo, CA, 1993."},{"key":"12_CR16","doi-asserted-by":"crossref","first-page":"226","DOI":"10.1137\/0204020","volume":"4","author":"R. Sethi","year":"1975","unstructured":"R. Sethi, Complete register allocation problems, SIAM J. Comput.\n4 (1975), pp. 226\u2013248.","journal-title":"SIAM J. Comput."},{"key":"12_CR17","doi-asserted-by":"crossref","first-page":"692","DOI":"10.1137\/0210052","volume":"10","author":"P. J. Slater","year":"1981","unstructured":"P. J. Slater, E. J. Cockayne, and S. T. Hedetniemi, Information dissemination in trees, SIAM J. Comput.\n10 (1981), pp. 692\u2013701.","journal-title":"SIAM J. Comput."},{"key":"12_CR18","doi-asserted-by":"crossref","first-page":"862","DOI":"10.1137\/0214061","volume":"14","author":"R. E. Tarjan","year":"1985","unstructured":"R. E. Tarjan and U. Vishkin, An efficient parallel biconnectivity algorithm, SIAM J. Comput.\n14 (1985), pp. 862\u2013874.","journal-title":"SIAM J. Comput."},{"key":"12_CR19","unstructured":"R. A. Wagner and Y. Han, Parallel algorithms for bucket sorting and the data dependent prefix problem, In Proc. International Conference on Parallel Processing (ICPP 1986), pp. 924\u2013930."}],"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-62559-3_12.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,28]],"date-time":"2021-04-28T01:38:33Z","timestamp":1619573913000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-62559-3_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997]]},"ISBN":["9783540625599","9783540680727"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/3-540-62559-3_12","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1997]]}}}