{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,1]],"date-time":"2026-06-01T07:03:42Z","timestamp":1780297422485,"version":"3.54.0"},"reference-count":56,"publisher":"Elsevier BV","issue":"1","license":[{"start":{"date-parts":[[1992,1,1]],"date-time":"1992-01-01T00:00:00Z","timestamp":694224000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[1992,1,1]],"date-time":"1992-01-01T00:00:00Z","timestamp":694224000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/legal\/tdmrep-license"},{"start":{"date-parts":[[2004,3,25]],"date-time":"2004-03-25T00:00:00Z","timestamp":1080172800000},"content-version":"vor","delay-in-days":4467,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc-nd\/4.0\/"}],"content-domain":{"domain":["elsevier.com","sciencedirect.com"],"crossmark-restriction":true},"short-container-title":["Theoretical Computer Science"],"published-print":{"date-parts":[[1992,1]]},"DOI":"10.1016\/0304-3975(92)90135-3","type":"journal-article","created":{"date-parts":[[2002,7,25]],"date-time":"2002-07-25T23:47:37Z","timestamp":1027640857000},"page":"49-76","update-policy":"https:\/\/doi.org\/10.1016\/elsevier_cm_policy","source":"Crossref","is-referenced-by-count":45,"title":["Dynamic programming with convexity, concavity and sparsity"],"prefix":"10.1016","volume":"92","author":[{"given":"Zvi","family":"Galil","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kunsoo","family":"Park","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"78","reference":[{"key":"10.1016\/0304-3975(92)90135-3_BIB1","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/0166-218X(90)90124-U","article-title":"Applications of generalized matrix searching to geometric algorithms","volume":"27","author":"Aggarwal","year":"1990","journal-title":"Discrete Applied Math."},{"key":"10.1016\/0304-3975(92)90135-3_BIB2","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1007\/BF01840359","article-title":"Geometric applications of a matrix-searching algorithm","volume":"2","author":"Aggarwal","year":"1987","journal-title":"Algorithmica"},{"key":"10.1016\/0304-3975(92)90135-3_BIB3","series-title":"Proc. 29th IEEE Symp. Found. Computer Science","first-page":"497","article-title":"Notes on searching in multidimensional monotone arrays","author":"Aggarwal","year":"1988"},{"key":"10.1016\/0304-3975(92)90135-3_BIB4","series-title":"The Design and Analysis of Computer Algorithms","author":"Aho","year":"1974"},{"key":"10.1016\/0304-3975(92)90135-3_BIB5","first-page":"1","article-title":"Bounds on the complexity of the longest common subsequence problem","volume":"23","author":"Aho","year":"1976","journal-title":"J. Assoc. Comput. Mach."},{"key":"10.1016\/0304-3975(92)90135-3_BIB6","series-title":"Data Structures and Algorithms","author":"Aho","year":"1983"},{"key":"10.1016\/0304-3975(92)90135-3_BIB7","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1007\/BF01840365","article-title":"The longest common subsequence problem revisited","volume":"2","author":"Apostolico","year":"1987","journal-title":"Algorithmica"},{"key":"10.1016\/0304-3975(92)90135-3_BIB8","series-title":"Dynamic Programming","author":"Bellman","year":"1957"},{"key":"10.1016\/0304-3975(92)90135-3_BIB9","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1145\/321105.321111","article-title":"Dynamic programming treatment of the traveling salesman problem","volume":"9","author":"Bellman","year":"1962","journal-title":"J. Assoc. Comput. Mach."},{"key":"10.1016\/0304-3975(92)90135-3_BIB10","doi-asserted-by":"crossref","first-page":"403","DOI":"10.1145\/356827.356831","article-title":"Tabulation techniques for recursive programs","volume":"12","author":"Bird","year":"1980","journal-title":"Computing Surveys"},{"key":"10.1016\/0304-3975(92)90135-3_BIB11","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1016\/0196-6774(90)90031-9","article-title":"Sequence comparison with mixed convex and concave costs","volume":"11","author":"Eppstein","year":"1990","journal-title":"J. Algorithms"},{"key":"10.1016\/0304-3975(92)90135-3_BIB12","series-title":"Proc. 29th IEEE Symp. Found. Computer Science","first-page":"488","article-title":"Speeding up dynamic programming","author":"Eppstein","year":"1988"},{"key":"10.1016\/0304-3975(92)90135-3_BIB13","unstructured":"D. Eppstein, Z. Galil, R. Giancarlo and G.F. Italiano, Sparse dynamic programming I: linear cost functions, J. Assoc. Comput. Mach., to appear."},{"key":"10.1016\/0304-3975(92)90135-3_BIB14","unstructured":"D. Eppstein, Z. Galil, R. Giancarlo and G.F. Italiano, Sparse dynamic programming II: convex and concave cost functions, J. Assoc. Comput. Mach., to appear."},{"key":"10.1016\/0304-3975(92)90135-3_BIB15","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1016\/0304-3975(89)90101-1","article-title":"Speeding up dynamic programming with applications to molecular biology","volume":"64","author":"Galil","year":"1989","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/0304-3975(92)90135-3_BIB16","series-title":"Proc. 16th ICALP","first-page":"394","article-title":"An improved algorithm for approximate string matching","volume":"Vol. 372","author":"Galil","year":"1989"},{"key":"10.1016\/0304-3975(92)90135-3_BIB17","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1016\/0020-0190(90)90215-J","article-title":"A linear-time algorithm for concave one-dimensional dynamic programming","volume":"33","author":"Galil","year":"1990","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/0304-3975(92)90135-3_BIB18","doi-asserted-by":"crossref","first-page":"705","DOI":"10.1016\/0022-2836(82)90398-9","article-title":"An improved algorithm for matching biological sequences","volume":"162","author":"Gotoh","year":"1982","journal-title":"J. Mol. Biol."},{"key":"10.1016\/0304-3975(92)90135-3_BIB19","series-title":"Proc. 8th ACM Symp. Theory of Computing","first-page":"112","article-title":"On-line context-free language recognition in less than cubic time","author":"Graham","year":"1976"},{"key":"10.1016\/0304-3975(92)90135-3_BIB20","doi-asserted-by":"crossref","first-page":"196","DOI":"10.1137\/0110015","article-title":"A dynamic programming approach to sequencing problems","volume":"10","author":"Held","year":"1962","journal-title":"SIAM J. Applied Math."},{"key":"10.1016\/0304-3975(92)90135-3_BIB21","doi-asserted-by":"crossref","first-page":"319","DOI":"10.1137\/0606032","article-title":"A comprehensive model of dynamic programming","volume":"6","author":"Helman","year":"1985","journal-title":"SIAM J. Alg. Dics. Meth."},{"issue":"6","key":"10.1016\/0304-3975(92)90135-3_BIB22","doi-asserted-by":"crossref","first-page":"341","DOI":"10.1145\/360825.360861","article-title":"A linear-space algorithm for computing maximal common subsequences","volume":"18","author":"Hirschberg","year":"1975","journal-title":"Comm. ACM"},{"key":"10.1016\/0304-3975(92)90135-3_BIB23","doi-asserted-by":"crossref","first-page":"664","DOI":"10.1145\/322033.322044","article-title":"Algorithms for the longest common subsequence problem","volume":"24","author":"Hirschberg","year":"1977","journal-title":"J. Assoc. Comput. Mach."},{"issue":"4","key":"10.1016\/0304-3975(92)90135-3_BIB24","doi-asserted-by":"crossref","first-page":"628","DOI":"10.1137\/0216043","article-title":"The least weight subsequences problem","volume":"16","author":"Hirschberg","year":"1987","journal-title":"SIAM J. Comput."},{"key":"10.1016\/0304-3975(92)90135-3_BIB25","first-page":"317","article-title":"On simple linear programming problems","volume":"Vol. 7","author":"Hoffman","year":"1963"},{"key":"10.1016\/0304-3975(92)90135-3_BIB26","series-title":"Introduction to Automata Theory, Languages, and Computation","author":"Hopcroft","year":"1979"},{"key":"10.1016\/0304-3975(92)90135-3_BIB27","doi-asserted-by":"crossref","first-page":"362","DOI":"10.1137\/0211028","article-title":"Computation of matrix chain products","volume":"11","author":"Hu","year":"1982","journal-title":"SIAM J. Comput."},{"key":"10.1016\/0304-3975(92)90135-3_BIB28","doi-asserted-by":"crossref","first-page":"228","DOI":"10.1137\/0213017","article-title":"Computation of matrix chain products","volume":"13","author":"Hu","year":"1984","journal-title":"SIAM J. Comput."},{"key":"10.1016\/0304-3975(92)90135-3_BIB29","doi-asserted-by":"crossref","first-page":"350","DOI":"10.1145\/359581.359603","article-title":"A fast algorithm for computing longest common subsequences","volume":"20","author":"Hunt","year":"1977","journal-title":"Comm. ACM"},{"key":"10.1016\/0304-3975(92)90135-3_BIB30","doi-asserted-by":"crossref","first-page":"295","DOI":"10.1007\/BF01786986","article-title":"A priority queue in which initialization and queue operations take O(log log D) time","volume":"15","author":"Johnson","year":"1982","journal-title":"Math. Systems Theory"},{"key":"10.1016\/0304-3975(92)90135-3_BIB31","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1093\/nar\/10.1.265","article-title":"Pattern recognition in nucleic acid sequences II: an efficient method for finding locally stable secondary structures","volume":"10","author":"Kanehisa","year":"1982","journal-title":"Nucl. Acids Res."},{"key":"10.1016\/0304-3975(92)90135-3_BIB32","doi-asserted-by":"crossref","first-page":"693","DOI":"10.1137\/0115060","article-title":"Finite-state processes and dynamic programming","volume":"15","author":"Karp","year":"1967","journal-title":"SIAM J. Applied Math."},{"key":"10.1016\/0304-3975(92)90135-3_BIB33","series-title":"Speeding up dynamic programming","author":"Klawe","year":"1987"},{"key":"10.1016\/0304-3975(92)90135-3_BIB34","series-title":"A simple linear-time algorithm for concave one-dimensional dynamic programming","author":"Klawe","year":"1990"},{"key":"10.1016\/0304-3975(92)90135-3_BIB35","series-title":"An almost linear time algorithm for generalized matrix searching","author":"Klawe","year":"1988"},{"key":"10.1016\/0304-3975(92)90135-3_BIB36","doi-asserted-by":"crossref","first-page":"14","DOI":"10.1007\/BF00264289","article-title":"Optimum binary search trees","volume":"1","author":"Knuth","year":"1971","journal-title":"Acta Informatica"},{"key":"10.1016\/0304-3975(92)90135-3_BIB37","unstructured":"L.L. Larmore, An optimal algorithm with unknown time complexity for convex matrix searching. Inform Process. Lett., to appear."},{"key":"10.1016\/0304-3975(92)90135-3_BIB38","unstructured":"L.L. Larmore and B. Schieber, On-line dynamic programming with applications to the prediction of RNA secondary structure, J. Algorithms, to appear."},{"key":"10.1016\/0304-3975(92)90135-3_BIB39","series-title":"Combinatorial Optimization: Networks and Matroids","author":"Lawler","year":"1976"},{"key":"10.1016\/0304-3975(92)90135-3_BIB40","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1016\/S0092-8240(88)80016-8","article-title":"Sequence comparison with concave weighting functions","volume":"50","author":"Miller","year":"1988","journal-title":"Bull. Math. Biol."},{"key":"10.1016\/0304-3975(92)90135-3_BIB41","series-title":"D\u00e9blai et remblai","author":"Monge","year":"1781"},{"key":"10.1016\/0304-3975(92)90135-3_BIB42","doi-asserted-by":"crossref","first-page":"443","DOI":"10.1016\/0022-2836(70)90057-4","article-title":"A general method applicable to the search for similarities in the amino acid sequence of two proteins","volume":"48","author":"Needleman","year":"1970","journal-title":"J. Mol. Biol."},{"key":"10.1016\/0304-3975(92)90135-3_BIB43","series-title":"Data Structures and Network Algorithms","author":"Tarjan","year":"1983"},{"key":"10.1016\/0304-3975(92)90135-3_BIB44","doi-asserted-by":"crossref","first-page":"100","DOI":"10.1016\/S0019-9958(85)80046-2","article-title":"Algorithms for approximate string matching","volume":"64","author":"Ukkonen","year":"1985","journal-title":"Inform. and Control"},{"key":"10.1016\/0304-3975(92)90135-3_BIB45","doi-asserted-by":"crossref","first-page":"308","DOI":"10.1016\/S0022-0000(75)80046-8","article-title":"General context-free recognition in less than cubic time","volume":"10","author":"Valiant","year":"1975","journal-title":"J. Comput. Systems Sci."},{"key":"10.1016\/0304-3975(92)90135-3_BIB46","series-title":"Proc. 16th IEEE Symp. Found. Computer Science","first-page":"75","article-title":"Preserving order in a forest in less than logarithmic time","author":"van Emde Boas","year":"1975"},{"key":"10.1016\/0304-3975(92)90135-3_BIB47","doi-asserted-by":"crossref","first-page":"80","DOI":"10.1016\/0020-0190(77)90031-X","article-title":"Preserving order in a forest in less than logarithmic time and linear space","volume":"6","author":"van Emde Boas","year":"1977","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/0304-3975(92)90135-3_BIB48","doi-asserted-by":"crossref","first-page":"518","DOI":"10.1016\/0196-6774(89)90003-5","article-title":"On an efficient dynamic programming technique of F.F. Yao","volume":"10","author":"Wachs","year":"1989","journal-title":"J. Algorithms"},{"key":"10.1016\/0304-3975(92)90135-3_BIB49","doi-asserted-by":"crossref","first-page":"168","DOI":"10.1145\/321796.321811","article-title":"The string-to-string correction problem","volume":"21","author":"Wagner","year":"1974","journal-title":"J. Assoc. Comput. Mach."},{"key":"10.1016\/0304-3975(92)90135-3_BIB50","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1016\/0025-5564(78)90099-8","article-title":"RNA secondary structure: a complete mathematical analysis","volume":"42","author":"Waterman","year":"1978","journal-title":"Math. Biosciences"},{"key":"10.1016\/0304-3975(92)90135-3_BIB51","doi-asserted-by":"crossref","first-page":"455","DOI":"10.1016\/0196-8858(86)90025-4","article-title":"Rapid dynamic programming algorithms for RNA secondary structure","volume":"7","author":"Waterman","year":"1986","journal-title":"Advances in Applied Math."},{"key":"10.1016\/0304-3975(92)90135-3_BIB52","doi-asserted-by":"crossref","first-page":"418","DOI":"10.1016\/0196-6774(88)90032-6","article-title":"The concave least-weight subsequence problem revisited","volume":"9","author":"Wilber","year":"1988","journal-title":"J. Algorithms"},{"key":"10.1016\/0304-3975(92)90135-3_BIB53","doi-asserted-by":"crossref","first-page":"557","DOI":"10.1137\/0144038","article-title":"The context-dependent comparison of biological sequences","volume":"44","author":"Wilbur","year":"1984","journal-title":"SIAM J. Applied Math."},{"key":"10.1016\/0304-3975(92)90135-3_BIB54","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1145\/321921.321923","article-title":"Bounds for the string editing problem","volume":"23","author":"Wong","year":"1976","journal-title":"J. Assoc. Comput. Mach."},{"key":"10.1016\/0304-3975(92)90135-3_BIB55","series-title":"Proc. 12th ACM Symp. Theory of Computing","first-page":"429","article-title":"Efficient dynamic programming using quadrangle inequalities","author":"Yao","year":"1980"},{"key":"10.1016\/0304-3975(92)90135-3_BIB56","doi-asserted-by":"crossref","first-page":"532","DOI":"10.1137\/0603055","article-title":"Speed-up in dynamic programming","volume":"3","author":"Yao","year":"1982","journal-title":"SIAM J. Alg. Disc. Meth."}],"container-title":["Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:0304397592901353?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:0304397592901353?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2026,6,1]],"date-time":"2026-06-01T06:48:05Z","timestamp":1780296485000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/0304397592901353"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1992,1]]},"references-count":56,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1992,1]]}},"alternative-id":["0304397592901353"],"URL":"https:\/\/doi.org\/10.1016\/0304-3975(92)90135-3","relation":{},"ISSN":["0304-3975"],"issn-type":[{"value":"0304-3975","type":"print"}],"subject":[],"published":{"date-parts":[[1992,1]]},"assertion":[{"value":"Elsevier","name":"publisher","label":"This article is maintained by"},{"value":"Dynamic programming with convexity, concavity and sparsity","name":"articletitle","label":"Article Title"},{"value":"Theoretical Computer Science","name":"journaltitle","label":"Journal Title"},{"value":"https:\/\/doi.org\/10.1016\/0304-3975(92)90135-3","name":"articlelink","label":"CrossRef DOI link to publisher maintained version"},{"value":"converted-article","name":"content_type","label":"Content Type"},{"value":"Copyright \u00a9 1992 Published by Elsevier B.V.","name":"copyright","label":"Copyright"}]}}