{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,22]],"date-time":"2025-03-22T04:19:09Z","timestamp":1742617149218,"version":"3.40.2"},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540565031"},{"type":"electronic","value":"9783540475743"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1993]]},"DOI":"10.1007\/3-540-56503-5_30","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T11:15:15Z","timestamp":1330254915000},"page":"294-305","source":"Crossref","is-referenced-by-count":3,"title":["Parallel algorithm for the matrix chain product and the optimal triangulation problems (extended abstract)"],"prefix":"10.1007","author":[{"given":"Artur","family":"Czumaj","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,27]]},"reference":[{"key":"30_CR1","doi-asserted-by":"crossref","unstructured":"M.J. Atallah, S.R. Kosajaru, L.L. Larmore, G.L. Miller, S-H. Teng, Constructing trees in parallel, SPAA 1989, pp. 421\u2013431.","DOI":"10.1145\/72935.72980"},{"key":"30_CR2","doi-asserted-by":"crossref","unstructured":"M.J. Atallah, S.R. Kosajaru, An efficient algorithm for the row minima of a totally monotone matrix, SODA 1991, pp. 394\u2013403.","DOI":"10.1016\/0196-6774(92)90046-F"},{"key":"30_CR3","unstructured":"P.G. Bradford, A parallel approximation algorithm for matrix chain ordering, manuscript, 1992."},{"key":"30_CR4","unstructured":"P.G. Bradford Efficient parallel dynamic programming, manuscript, 1992."},{"key":"30_CR5","doi-asserted-by":"crossref","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. Assoc. Comput. Mach., 21 (1974), pp. 201\u2013206.","journal-title":"J. Assoc. Comput. Mach."},{"key":"30_CR6","doi-asserted-by":"crossref","unstructured":"K.F. Chan, T.W. Lam, Finding least-weight subsequences with fewer processors, SIGAL 1990, LNCS 450, pp. 318\u2013327, also to appear in Algorithmica.","DOI":"10.1007\/3-540-52921-7_81"},{"key":"30_CR7","doi-asserted-by":"crossref","unstructured":"R. Cole, U. Vishkin, Approximate and exact parallel scheduling with applications to list, tree and graph problems, FOCS 1986, pp. 478\u2013491.","DOI":"10.1109\/SFCS.1986.10"},{"key":"30_CR8","doi-asserted-by":"crossref","unstructured":"A. Czumaj, An optimal parallel algorithm for computing a near-optimal order of matrix multiplications, SWAT 1992, LNCS 621, pp. 62\u201372.","DOI":"10.1007\/3-540-55706-7_6"},{"issue":"9","key":"30_CR9","doi-asserted-by":"crossref","first-page":"864","DOI":"10.1109\/TC.1973.5009182","volume":"C-22","author":"S. S. Godbole","year":"1973","unstructured":"S.S. Godbole, On efficient computation of matrix chain products, IEEE Trans. Comput., C-22, 9 (1973), pp. 864\u2013866.","journal-title":"IEEE Trans. Comput."},{"key":"30_CR10","unstructured":"Z. Galil, K. Park, Parallel dynamic programming, manuscript, 1992, submitted to J. Parallel Distrib. Comput."},{"key":"30_CR11","unstructured":"A.M. Gibbons, W. Rytter, Efficient parallel algorithms, Cambridge University Press, 1988."},{"key":"30_CR12","doi-asserted-by":"crossref","unstructured":"S-H.S. Huang, H. Liu, V. Viswanathan, Parallel dynamic programming, IEEE Symposium on Parallel and Distributed Processing, 1990, pp. 497\u2013500.","DOI":"10.1109\/SPDP.1990.143590"},{"key":"30_CR13","doi-asserted-by":"crossref","unstructured":"T.C. Hu, M.T. Shing, Some theorems about matrix multiplications, FOCS 1980, pp. 28\u201335.","DOI":"10.1109\/SFCS.1980.39"},{"key":"30_CR14","doi-asserted-by":"crossref","first-page":"362","DOI":"10.1137\/0211028","volume":"11","author":"T. C. Hu","year":"1982","unstructured":"T.C. Hu, M.T. Shing, Computation of matrix chain products. Part I, SIAM J. Comput., 11(1982), pp. 362\u2013373.","journal-title":"SIAM J. Comput."},{"key":"30_CR15","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1137\/0403009","volume":"3","author":"M. M. Klawe","year":"1990","unstructured":"M.M. Klawe, D.J. Kleitman, An almost linear time algorithm for generalized matrix searching, SIAM J. Discrete Math., 3 (1990), pp. 81\u201397.","journal-title":"SIAM J. Discrete Math."},{"key":"30_CR16","doi-asserted-by":"crossref","unstructured":"R.M. Karp, V. Ramachandran, A survey of parallel algorithms for sharedmemory machines, in Handbook of Theoretical Computer Science, North-Holland, 1990, pp. 869\u2013941.","DOI":"10.1016\/B978-0-444-88071-0.50022-9"},{"key":"30_CR17","unstructured":"P. Ramanan, A new lower bound technique and its application: tight lower bound for a polygon triangulation problem, SODA 1991, pp. 281\u2013290."},{"key":"30_CR18","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1016\/0304-3975(88)90147-8","volume":"59","author":"W. Rytter","year":"1988","unstructured":"W. Rytter, On efficient parallel computations for some dynamic programming problems, Theoret. Comput. Sci., 59 (1988), pp. 297\u2013307.","journal-title":"Theoret. Comput. Sci."},{"key":"30_CR19","doi-asserted-by":"crossref","first-page":"641","DOI":"10.1137\/0212043","volume":"12","author":"L. Valiant","year":"1983","unstructured":"L. Valiant, S. Skyum, S. Berkowitz, C. Rackoff, Fast parallel computation of polynomials using few processors, SIAM J. Comput., 12 (1983), pp. 641\u2013644.","journal-title":"SIAM J. Comput."},{"key":"30_CR20","doi-asserted-by":"crossref","first-page":"532","DOI":"10.1137\/0603055","volume":"3","author":"F. F. Yao","year":"1982","unstructured":"F.F. Yao, Speed-up in dynamic programming, SIAM J. Algebraic and Discrete Methods, 3 (1982), pp. 532\u2013540.","journal-title":"SIAM J. Algebraic and Discrete Methods"}],"container-title":["Lecture Notes in Computer Science","STACS 93"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-56503-5_30.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T21:49:41Z","timestamp":1742593781000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-56503-5_30"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993]]},"ISBN":["9783540565031","9783540475743"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/3-540-56503-5_30","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1993]]}}}