{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T22:26:25Z","timestamp":1725575185743},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540240136"},{"type":"electronic","value":"9783540305019"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-30501-9_48","type":"book-chapter","created":{"date-parts":[[2011,1,14]],"date-time":"2011-01-14T02:42:17Z","timestamp":1294972937000},"page":"218-225","source":"Crossref","is-referenced-by-count":3,"title":["O(1) Time Algorithm on BSR for Constructing a Binary Search Tree with Best Frequencies"],"prefix":"10.1007","author":[{"given":"Limin","family":"Xiang","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kazuo","family":"Ushijiam","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kai","family":"Cheng","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jianjun","family":"Zhao","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Cunwei","family":"Lu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"6","key":"48_CR1","doi-asserted-by":"publisher","first-page":"1141","DOI":"10.1137\/S0097539792224954","volume":"24","author":"L. Devroye","year":"1995","unstructured":"Devroye, L., Robson, J.M.: On the generation of random binary search tree. SIAM J. Comput.\u00a024(6), 1141\u20131156 (1995)","journal-title":"SIAM J. Comput."},{"issue":"9","key":"48_CR2","doi-asserted-by":"publisher","first-page":"912","DOI":"10.1109\/71.954621","volume":"12","author":"L. Xiang","year":"2001","unstructured":"Xiang, L., Ushijima, K.: On time bounds, the work-time scheduling principle, and optimality for BSR. IEEE Trans. on Parallel and Distributed Systems\u00a012(9), 912\u2013921 (2001)","journal-title":"IEEE Trans. on Parallel and Distributed Systems"},{"key":"48_CR3","first-page":"475","volume-title":"Parallel Computation: Models and Methods","author":"S.G. Akl","year":"1997","unstructured":"Akl, S.G.: Parallel Computation: Models and Methods, pp. 475\u2013509. Prentice Hall, N.J (1997)"},{"issue":"3","key":"48_CR4","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1109\/71.210809","volume":"4","author":"L.F. Lindon","year":"1993","unstructured":"Lindon, L.F., Akl, S.G.: An Optimal Implementation of Broadcasting with Selective Reduction. IEEE Trans. on Parallel and Distributed Systems\u00a04(3), 256\u2013269 (1993)","journal-title":"IEEE Trans. on Parallel and Distributed Systems"},{"issue":"8","key":"48_CR5","doi-asserted-by":"publisher","first-page":"852","DOI":"10.1109\/71.790602","volume":"10","author":"L. Xiang","year":"1999","unstructured":"Xiang, L., Ushijima, K., Akl, S.G., Stojmenovic, I.: An Efficient Implementation for the BROADCAST Instruction of BSR+. IEEE Trans. on Parallel and Distributed Systems\u00a010(8), 852\u2013863 (1999)","journal-title":"IEEE Trans. on Parallel and Distributed Systems"},{"issue":"2","key":"48_CR6","doi-asserted-by":"publisher","first-page":"218","DOI":"10.1109\/71.485530","volume":"7","author":"I. Stojmenovic","year":"1996","unstructured":"Stojmenovic, I.: Constant time BSR solutions to parenthesis matching, tree decoding, and tree reconstruction from its traversals. IEEE Trans. on Parallel and Distributed Systems\u00a07(2), 218\u2013224 (1996)","journal-title":"IEEE Trans. on Parallel and Distributed Systems"},{"key":"48_CR7","unstructured":"Xiang, L., Ushijima, K.: Decoding and drawing an arbitrary tree from its pre-post sequence. In: Proc. PDCS 1998, Las Vegas, pp. 182\u2013185 (1998)"},{"key":"48_CR8","unstructured":"Xiang, L., Ushijima, K.: Optimal Parallel Merging Algorithms on BSR. In: Proc. I-SPAN 2000, Dallas, pp. 12\u201317 (2000)"},{"key":"48_CR9","unstructured":"Xiang, L., Ushijima, K.: O(1) Time Algorithm on BSR for Computing Convex Hull. In: Proc. PDCS 2002, Cambridge, USA, pp. 143\u2013146 (2002)"},{"issue":"3","key":"48_CR10","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1016\/S0020-0190(97)00214-7","volume":"65","author":"L. Xiang","year":"1998","unstructured":"Xiang, L., Ushijima, K.: ANSV problem on BSRs. Information Processing Letters\u00a065(3), 135\u2013138 (1998)","journal-title":"Information Processing Letters"},{"issue":"1","key":"48_CR11","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1142\/S0129626499000128","volume":"9","author":"L. Xiang","year":"1999","unstructured":"Xiang, L., Ushijima, K.: Decoding and drawing on BSR for a binary tree from its i-p sequence. Parallel Processing Letters\u00a09(1), 103\u2013110 (1999)","journal-title":"Parallel Processing Letters"},{"issue":"1","key":"48_CR12","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1016\/S0020-0190(99)00085-X","volume":"71","author":"L. Xiang","year":"1999","unstructured":"Xiang, L., Ushijima, K.: Rearranging scattered information on BSR. Information Processing Letters\u00a071(1), 43\u201347 (1999)","journal-title":"Information Processing Letters"},{"issue":"2","key":"48_CR13","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1016\/S0020-0190(99)00086-1","volume":"71","author":"L. Xiang","year":"1999","unstructured":"Xiang, L., Ushijima, K.: A theorem on the relation between BSR\n                              \n                      k\n                     and BSR\n                              \u2009+\u2009. Information Processing Letters\u00a071(2), 71\u201373 (1999)","journal-title":"Information Processing Letters"},{"issue":"3-4","key":"48_CR14","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1142\/S0129626402001051","volume":"12","author":"L. Xiang","year":"2002","unstructured":"Xiang, L., Ushijima, K., Zhao, J.: Time Optimal n-Size Matching Parentheses and Binary Tree Decoding Algorithms on a p-Processor BSR. Parallel Processing Letters\u00a012(3-4), 365\u2013374 (2002)","journal-title":"Parallel Processing Letters"},{"key":"48_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"218","DOI":"10.1007\/978-3-540-30501-9_48","volume-title":"Parallel and Distributed Computing: Applications and Technologies","author":"L. Xiang","year":"2004","unstructured":"Xiang, L., Ushijima, K., Zhao, J., Zhang, T., Tang, C.: O(1) Time Algorithm on BSR for Constructing a Random Binary Search Tree. In: Liew, K.-M., Shen, H., See, S., Cai, W. (eds.) PDCAT 2004. LNCS, vol.\u00a03320, pp. 218\u2013225. Springer, Heidelberg (2004)"}],"container-title":["Lecture Notes in Computer Science","Parallel and Distributed Computing: Applications and Technologies"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-30501-9_48.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,3]],"date-time":"2021-05-03T03:25:23Z","timestamp":1620012323000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-30501-9_48"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540240136","9783540305019"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-30501-9_48","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2004]]}}}