{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T16:38:25Z","timestamp":1725467905276},"publisher-location":"Berlin\/Heidelberg","reference-count":19,"publisher":"Springer-Verlag","isbn-type":[{"type":"print","value":"0387968180"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/bfb0040377","type":"book-chapter","created":{"date-parts":[[2006,8,2]],"date-time":"2006-08-02T20:03:50Z","timestamp":1154549030000},"page":"91-100","source":"Crossref","is-referenced-by-count":12,"title":["Optimal parallel algorithms for expression tree evaluation and list ranking"],"prefix":"10.1007","author":[{"given":"Richard","family":"Cole","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Uzi","family":"Vishkin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"10_CR1","unstructured":"R.J. Anderson and G.L. Miller, Optimal parallel algorithms for list ranking, this proceedings."},{"issue":"2","key":"10_CR2","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1145\/321812.321815","volume":"21","author":"R.P. Brent","year":"1974","unstructured":"R.P. Brent, \"The parallel evaluation of general arithmetic expressions\", J. ACM 21,2 (1974), 201\u2013206.","journal-title":"J. ACM"},{"issue":"2","key":"10_CR3","doi-asserted-by":"publisher","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. on Prog. Lang. and Sys. 7,2 (1985), 348\u2013357.","journal-title":"ACM Trans. on Prog. Lang. and Sys."},{"key":"10_CR4","doi-asserted-by":"publisher","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, Information and Control 70 (1986), 32\u201353.","journal-title":"Information and Control"},{"key":"10_CR5","doi-asserted-by":"crossref","unstructured":"R. Cole and U. Vishkin, Approximate and exact parallel scheduling with applications to list, tree and graph problems, Proc. 27th Symp. on Foundations of Computer Science, 1986, 478\u2013491.","DOI":"10.1109\/SFCS.1986.10"},{"key":"10_CR6","unstructured":"R. Cole and U. Vishkin, The accelerated centroid decomposition technique for optimal parallel tree evaluation in logarithmic time, Computer Science Department Technical Report #242, Courant Institute, 1986."},{"key":"10_CR7","doi-asserted-by":"crossref","unstructured":"R. Cole and U. Vishkin, \"Approximate parallel scheduling. Part I: The basic technique with applications to optimal parallel list ranking in logarithmic time\", to appear, SIAM Journal on Computing.","DOI":"10.1137\/0217009"},{"key":"10_CR8","doi-asserted-by":"crossref","unstructured":"A. Goldberg, S. Plotkin, and G. Shannon, \"Parallel symmetry-breaking in sparse graphs\", Nineteenth Annual ACM Symp. on Theory of Computing, 315\u2013224.","DOI":"10.21236\/ADA198233"},{"key":"10_CR9","unstructured":"H. Gazit, G. Miller and S. H. Teng, Optimal tree contraction in EREW model, manuscript, Computer Science Department, University of Southern California."},{"key":"10_CR10","series-title":"Research Report","volume-title":"An optimal parallel algorithm for dynamic tree expression evaluation and its applications","author":"A. Gibbons","year":"1986","unstructured":"A. Gibbons and W. Rytter, An optimal parallel algorithm for dynamic tree expression evaluation and its applications, Research Report 77, Dept. of Computer Science, Univ. of Warwick, Coventry, CV4 7AL, England, 1986."},{"key":"10_CR11","volume-title":"The general tree algebraic computations and its applications in parallel algorithms design","author":"X. He","year":"1986","unstructured":"X. He, The general tree algebraic computations and its applications in parallel algorithms design, preprint, 1986, Dept. of Computer and Information Science, Ohio State University, Columbus, OH 43210."},{"key":"10_CR12","doi-asserted-by":"publisher","first-page":"853","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, JACM 30(1983), 853\u2013865.","journal-title":"JACM"},{"key":"10_CR13","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, 478\u2013489.","DOI":"10.1109\/SFCS.1985.43"},{"key":"10_CR14","doi-asserted-by":"crossref","unstructured":"J.H. Reif, An optimal parallel algorithm for integer sorting, Proc. 26th Symp. on Foundations of Computer Science, 1985, 496\u2013503, to appear SIAM J. Comput.","DOI":"10.1109\/SFCS.1985.9"},{"issue":"4","key":"10_CR15","doi-asserted-by":"publisher","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":"10_CR16","unstructured":"U. Vishkin, Synchronous parallel computation \u2014 a survey, TR 71, Dept. of Computer Science, Courant Institute, New York University, 1983."},{"key":"10_CR17","doi-asserted-by":"publisher","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, Information Processing Letters 20 (1985), 235\u2013240.","journal-title":"Information Processing Letters"},{"key":"10_CR18","doi-asserted-by":"publisher","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, JACM 22(1975), 477\u2013492.","journal-title":"JACM"},{"key":"10_CR19","volume-title":"The Complexity of Parallel Computation","author":"J.C. Wyllie","year":"1979","unstructured":"J.C. Wyllie, \"The Complexity of Parallel Computation\", Ph.D. thesis, TR 79-387, Dept. of Computer Science, Cornell Univ., Ithaca, NY, 1979."}],"container-title":["Lecture Notes in Computer Science","VLSI Algorithms and Architectures"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0040377.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,12,9]],"date-time":"2020-12-09T16:40:13Z","timestamp":1607532013000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0040377"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["0387968180"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/bfb0040377","relation":{},"subject":[]}}