{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,8]],"date-time":"2026-07-08T03:28:27Z","timestamp":1783481307361,"version":"3.55.0"},"reference-count":19,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[1994,9,1]],"date-time":"1994-09-01T00:00:00Z","timestamp":778377600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[1994,9,1]],"date-time":"1994-09-01T00:00:00Z","timestamp":778377600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[1994,9]]},"DOI":"10.1007\/bf02574380","type":"journal-article","created":{"date-parts":[[2007,3,22]],"date-time":"2007-03-22T12:11:43Z","timestamp":1174565503000},"page":"263-280","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":54,"title":["Finding a minimum-weightk-link path in graphs with the concave Monge property and applications"],"prefix":"10.1007","volume":"12","author":[{"given":"A.","family":"Aggarwal","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"B.","family":"Schieber","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"T.","family":"Tokuyama","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[1994,9,1]]},"reference":[{"key":"BF02574380_CR1","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1007\/BF01840359","volume":"2","author":"A. Aggarwal","year":"1987","unstructured":"A. Aggarwal, M. Klawe, S. Moran, P. Shor, and R. Wilber, Geometric Applications of a Matrix-Searching Algorithm,Algorithmica\n2 (1987), 195\u2013208.","journal-title":"Algorithmica"},{"key":"BF02574380_CR2","doi-asserted-by":"crossref","unstructured":"A. Aggarwal and J. Park, Notes on Searching in Multidimensional Monotone Arrays,Proc. 29th IEEE Symp. on Foundations on Computer Science, 1988, pp. 497\u2013512.","DOI":"10.1109\/SFCS.1988.21966"},{"key":"BF02574380_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"466","DOI":"10.1007\/3-540-57568-5_278","volume-title":"Consecutive Interval Query and Dynamic Programming on Intervals","author":"A. Aggarwal","year":"1993","unstructured":"A. Aggarwal and T. Tokuyama, Consecutive Interval Query and Dynamic Programming on Intervals,Proc. 4th Internat. Symp. on Algorithms and Computing, 1993, pp. 466\u2013475. Lecture Notes in Computer Science, Vol. 762. Springer-Verlag, Berlin."},{"key":"BF02574380_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1007\/3-540-54945-5_63","volume-title":"Dynamic Programming on Intervals","author":"T. Asano","year":"1991","unstructured":"T. Asano, Dynamic Programming on Intervals,Proc. 2nd Internat. Symp. on Algorithms, 1991, pp. 199\u2013207. Lecture Notes in Computer Science, Vol. 557. Springer-Verlag, Berlin."},{"key":"BF02574380_CR5","unstructured":"W. Bein, L. Larmore, and J. Park, Thed-Edge Shortest-Path Problem for a Monge Graph, Preprint, 1992."},{"key":"BF02574380_CR6","doi-asserted-by":"publisher","first-page":"134","DOI":"10.1137\/0214011","volume":"14","author":"J. Boyce","year":"1985","unstructured":"J. Boyce, D. Dobkin, R. Drysdale, and L. Guibas, Finding Extremal Polygons,SIAM J. Comput.\n14 (1985), 134\u2013147.","journal-title":"SIAM J. Comput."},{"key":"BF02574380_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"318","DOI":"10.1007\/3-540-52921-7_81","volume-title":"Finding Least-Weight Subsequences with Fewer Processors","author":"K. Chan","year":"1990","unstructured":"K. Chan and T. Lam, Finding Least-Weight Subsequences with Fewer Processors,Proc. SIGAL Internat. Symp. on Algorithms, 1990, pp. 318\u2013327. Lecture Notes in Computer Science, Vol. 450. Springer-Verlag, Berlin."},{"key":"BF02574380_CR8","doi-asserted-by":"crossref","unstructured":"B. Chazelle, H. Edelsbrunner, L. Guibas, and M. Sharir, Diameter, Width, Closest Line Pair, and Parametric Searching,Proc. 8th ACM Symp. on Computational Geometry, 1992, pp. 120\u2013129.","DOI":"10.1145\/142675.142702"},{"key":"BF02574380_CR9","doi-asserted-by":"publisher","first-page":"200","DOI":"10.1145\/7531.7537","volume":"34","author":"R. Cole","year":"1987","unstructured":"R. Cole, Slowing Down Sorting Networks to Obtain Faster Sorting Algorithms,J. Assoc. Comput. Mach.\n34 (1987), 200\u2013208.","journal-title":"J. Assoc. Comput. Mach."},{"key":"BF02574380_CR10","unstructured":"G. Frederickson, Optimal Algorithms for Tree Partitioning,Proc. 2nd ACM-SIAM Symp. on Discrete Algorithms, 1991, pp. 168\u2013177."},{"key":"BF02574380_CR11","series-title":"Technical Report 89-16","volume-title":"A Simple Linear-Time Algorithm for Concave One-Dimensional Dynamic Programming","author":"M. Klawe","year":"1989","unstructured":"M. Klawe, A Simple Linear-Time Algorithm for Concave One-Dimensional Dynamic Programming, Technical Report 89-16, University of British Columbia, Vancouver, 1989."},{"key":"BF02574380_CR12","unstructured":"M. Klawe and D. Kleitman, An Almost Linear-Time Algorithm for Generalized Matrix Searching, Technical Report RJ6275, IBM Almaden Research Center, 1988."},{"key":"BF02574380_CR13","doi-asserted-by":"publisher","first-page":"942","DOI":"10.1109\/TC.1983.1676138","volume":"32","author":"C. P. Kruskal","year":"1983","unstructured":"C. P. Kruskal, Searching, Merging and Sorting in Parallel Computation,IEEE Trans. Comput.\n32 (1983), 942\u2013946.","journal-title":"IEEE Trans. Comput."},{"key":"BF02574380_CR14","unstructured":"L. Larmore and D. Hirschberg, Length-Limited Coding,Proc. 1st ACM-SIAM Symp. on Discrete Algorithms, 1990, pp. 310\u2013318."},{"key":"BF02574380_CR15","doi-asserted-by":"crossref","unstructured":"L. Larmore and T. Przytycka, Parallel Construction of Trees with Optimal Weighted Path Length,Proc. 3rd ACM Symp. on Parallel Algorithms and Architectures, 1991, pp. 71\u201380.","DOI":"10.1145\/113379.113386"},{"key":"BF02574380_CR16","doi-asserted-by":"publisher","first-page":"490","DOI":"10.1016\/0196-6774(91)90016-R","volume":"12","author":"L. Larmore","year":"1991","unstructured":"L. Larmore and B. Schieber, On-Line Dynamic Programming with Applications to the Prediction of RNA Secondary Structure,J. Algorithms\n12 (1991), 490\u2013515.","journal-title":"J. Algorithms"},{"key":"BF02574380_CR17","doi-asserted-by":"publisher","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.\n30 (1983), 852\u2013865.","journal-title":"J. Assoc. Comput. Mach."},{"key":"BF02574380_CR18","doi-asserted-by":"publisher","first-page":"418","DOI":"10.1016\/0196-6774(88)90032-6","volume":"9","author":"R. Wilber","year":"1988","unstructured":"R. Wilber, The Concave Least Weight Subsequence Problem Revisited,J. Algorithms\n9 (1988), 418\u2013425.","journal-title":"J. Algorithms"},{"key":"BF02574380_CR19","doi-asserted-by":"publisher","first-page":"663","DOI":"10.1016\/0196-6774(91)90039-2","volume":"12","author":"X. Wu","year":"1991","unstructured":"X. Wu, Optimal Quantization by Matrix Searching,J. Algorithms\n12 (1991), 663\u2013673.","journal-title":"J. Algorithms"}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02574380.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/BF02574380\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02574380","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02574380.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,4,19]],"date-time":"2024-04-19T05:02:43Z","timestamp":1713502963000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/BF02574380"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994,9]]},"references-count":19,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1994,9]]}},"alternative-id":["BF02574380"],"URL":"https:\/\/doi.org\/10.1007\/bf02574380","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[1994,9]]},"assertion":[{"value":"23 March 1993","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 November 1993","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 September 1994","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}