{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T14:34:56Z","timestamp":1781015696214,"version":"3.54.1"},"reference-count":15,"publisher":"Springer Science and Business Media LLC","issue":"1-4","license":[{"start":{"date-parts":[[1988,11,1]],"date-time":"1988-11-01T00:00:00Z","timestamp":594345600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[1988,11]]},"DOI":"10.1007\/bf01762121","type":"journal-article","created":{"date-parts":[[2005,6,16]],"date-time":"2005-06-16T10:22:38Z","timestamp":1118917358000},"page":"329-346","source":"Crossref","is-referenced-by-count":66,"title":["The accelerated centroid decomposition technique for optimal parallel tree evaluation in logarithmic time"],"prefix":"10.1007","volume":"3","author":[{"given":"Richard","family":"Cole","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Uzi","family":"Vishkin","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"BF01762121_CR1","doi-asserted-by":"crossref","unstructured":"R. J. Anderson and G. L. Miller, Deterministic parallel list ranking, to appear, Aegean Workshop on Computing, Corfu, 1988.","DOI":"10.1007\/BFb0040376"},{"issue":"2","key":"BF01762121_CR2","doi-asserted-by":"crossref","first-page":"348","DOI":"10.1145\/3318.3478","volume":"7","author":"I. Bar-On","year":"1985","unstructured":"I. Bar-On and U. Vishkin, Optimal parallel generation of a computation tree form,ACM Trans. Prog. Lang. Sys.,7, 2 (1985), 348\u2013357.","journal-title":"ACM Trans. Prog. Lang. Sys."},{"key":"BF01762121_CR3","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,70 (1986), 32\u201353.","journal-title":"Inform, and Control"},{"issue":"1","key":"BF01762121_CR4","doi-asserted-by":"crossref","first-page":"128","DOI":"10.1137\/0217009","volume":"17","author":"R. Cole","year":"1988","unstructured":"R. Cole and U. Vishkin, Approximate parallel scheduling. Part I: The basic technique with applications to optimal parallel list ranking in logarithmic time,SIAM J. Comput.,17, 1 (1988), 128\u2013142.","journal-title":"SIAM J. Comput."},{"key":"BF01762121_CR5","unstructured":"R. Cole and U. Vishkin, Faster optimal parallel prefix sums and list ranking, Technical Report No. 277, Courant Institute, New York University, 1987; to appear,Inform, and Computation."},{"key":"BF01762121_CR6","unstructured":"H. Gazit, G. L. Miller, and S.-H. Teng, Optimal tree contraction in the EREW model, to appear,Princeton Workshop Book, Plenum, New York."},{"key":"BF01762121_CR7","doi-asserted-by":"crossref","unstructured":"A. Gibbons and W. Rytter, An optimal parallel algorithm for dynamic tree expression evaluation and its applications, Research Report 77, Department of Computer Science, University of Warwick, Coventry CV47AL, 1986.","DOI":"10.1007\/3-540-17179-7_28"},{"key":"BF01762121_CR8","volume-title":"The general tree algebraic computations and its applications in parallel algorithms design, Preprint","author":"X. He","year":"1986","unstructured":"X. He, The general tree algebraic computations and its applications in parallel algorithms design, Preprint, Department of Computer and Information Science, Ohio State University, Columbus, OH 43210, 1986."},{"key":"BF01762121_CR9","doi-asserted-by":"crossref","first-page":"852","DOI":"10.1145\/2157.322410","volume":"30","author":"N. Megiddo","year":"1983","unstructured":"N. Megiddo, Applying parallel computation algorithms in the design of serial algorithms,J. Assoc. Comput. Mach.,30 (1983), 852\u2013865.","journal-title":"J. Assoc. Comput. Mach."},{"key":"BF01762121_CR10","doi-asserted-by":"crossref","unstructured":"G. L. Miller and J. H. Reif, Parallel tree contraction and its applications,Proc. 26th Symp. on Foundations of Computer Science, 1985, pp. 478\u2013489; to appear asParallel Tree Contraction. Part 1: Fundamentals, Randomness, and Computation (S. Micali, ed.), JAI Press, Greenwich, CT;Parallel Tree Contraction. Part 2: Further Applications, submitted for publication.","DOI":"10.1109\/SFCS.1985.43"},{"key":"BF01762121_CR11","doi-asserted-by":"crossref","unstructured":"J. H. Reif, An optimal parallel algorithm for integer sorting,Proc. 26th Symp. on Foundations of Computer Science, 1985, pp. 496\u2013503; to appear,SIAM J. Comput.","DOI":"10.1109\/SFCS.1985.9"},{"issue":"4","key":"BF01762121_CR12","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.,14, 4 (1985), 862\u2013874.","journal-title":"SIAM J. Comput."},{"key":"BF01762121_CR13","unstructured":"U. Vishkin, Synchronous parallel computation\u2014a survey, Technical Report No. 71, Department of Computer Science, Courant Institute, New York University, 1983."},{"key":"BF01762121_CR14","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1016\/0020-0190(85)90025-0","volume":"20","author":"U. Vishkin","year":"1985","unstructured":"U. Vishkin, On efficient parallel strong orientation,Inform. Process. Lett.,20 (1985), 235\u2013240.","journal-title":"Inform. Process. Lett."},{"key":"BF01762121_CR15","doi-asserted-by":"crossref","first-page":"477","DOI":"10.1145\/321906.321911","volume":"22","author":"S. Winograd","year":"1975","unstructured":"S. Winograd, On the evaluation of certain arithmetic expressions,J. Assoc. Comput. Mach.,22 (1975), 477\u2013492.","journal-title":"J. Assoc. Comput. Mach."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01762121.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01762121\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01762121","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,7]],"date-time":"2020-04-07T19:26:46Z","timestamp":1586287606000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01762121"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1988,11]]},"references-count":15,"journal-issue":{"issue":"1-4","published-print":{"date-parts":[[1988,11]]}},"alternative-id":["BF01762121"],"URL":"https:\/\/doi.org\/10.1007\/bf01762121","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[1988,11]]}}}