{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,28]],"date-time":"2025-03-28T02:52:33Z","timestamp":1743130353400,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540440406"},{"type":"electronic","value":"9783540456872"}],"license":[{"start":{"date-parts":[[2002,1,1]],"date-time":"2002-01-01T00:00:00Z","timestamp":1009843200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2002,1,1]],"date-time":"2002-01-01T00:00:00Z","timestamp":1009843200000},"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":[],"published-print":{"date-parts":[[2002]]},"DOI":"10.1007\/3-540-45687-2_8","type":"book-chapter","created":{"date-parts":[[2007,10,19]],"date-time":"2007-10-19T08:57:47Z","timestamp":1192784267000},"page":"104-117","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Fast Algorithms with Algebraic Monge Properties"],"prefix":"10.1007","author":[{"given":"Wolfgang W.","family":"Bein","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Peter","family":"Brucker","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lawrence L.","family":"Larmore","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"James K.","family":"Park","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2002,10,4]]},"reference":[{"issue":"2","key":"8_CR1","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1007\/BF01840359","volume":"2","author":"A. Aggarwal","year":"1987","unstructured":"A. Aggarwal, M. M. Klawe, S. Moran, P. Shor, and R. Wilber. Geometric applications of a matrix-searching algorithm. Algorithmica, 2(2):195\u2013208, 1987.","journal-title":"Algorithmica"},{"key":"8_CR2","doi-asserted-by":"crossref","unstructured":"P. K. Agarwal and S. Sen. Selection in monotone matrices and computing k\n                           th nearest neighbors. In Proceedings of the 4th Scandinavian Workshop on Algorithm Theory, 1994.","DOI":"10.1007\/3-540-58218-5_2"},{"key":"8_CR3","doi-asserted-by":"crossref","unstructured":"A. Aggarwal, B. Schieber, and T. Tokuyama. Finding a minimum weight k-link path in graphs with Monge property and applications. In Proc. 9th Annu. ACM Sympos. Comput. Geom., pages 189\u2013197, 1993.","DOI":"10.1145\/160985.161135"},{"key":"8_CR4","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1007\/BF02574380","volume":"12","author":"A. Aggarwal","year":"1994","unstructured":"A. Aggarwal, B. Schieber, and T. Tokuyama. Finding a minimum-weight k-link path in graphs with the concave Monge property and applications. Discrete Comput. Geom., 12:263\u2013280, 1994.","journal-title":"Discrete Comput. Geom."},{"issue":"1","key":"8_CR5","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1016\/0166-218X(91)90024-Q","volume":"32","author":"R. E. Burkard","year":"1991","unstructured":"R. E. Burkard and W. Sandholzer. Efficiently solvable special cases of bottleneck travelling salesman problems. Discrete Applied Mathematics, 32(1):61\u201376, 1991.","journal-title":"Discrete Applied Mathematics"},{"key":"8_CR6","first-page":"63","volume":"32","author":"R. E. Burkard","year":"1979","unstructured":"R. E. Burkard. Remarks on some scheduling problems with algebraic objective functions. Operations Research Verfahren, 32:63\u201377, 1979.","journal-title":"Operations Research Verfahren"},{"key":"8_CR7","first-page":"391","volume-title":"Modern Applied Mathematics: Optimization and Operations Research","author":"R. E. Burkard","year":"1982","unstructured":"R. E. Burkard and U. Zimmermann. Combinatorial optimization in linearly ordered semimodules: A survey. In B. Korte, editor, Modern Applied Mathematics: Optimization and Operations Research, pages 391\u2013436. North-Holland Publishing Company, Amsterdam, Holland, 1982."},{"key":"8_CR8","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1016\/0166-218X(95)00103-X","volume":"70","author":"R. E. Burkard","year":"1996","unstructured":"R. E. Burkard and B. Klinz and R. Rudolf. Perspectives of monge properties in optimization. Discrete Applied Mathematics, 70:95\u2013161, 1996.","journal-title":"Discrete Applied Mathematics"},{"issue":"4","key":"8_CR9","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1016\/0022-0000(82)90048-4","volume":"24","author":"G. N. Frederickson","year":"1982","unstructured":"G. N. Frederickson and D. B. Johnson. The complexity of selection and ranking in X + Y and matrices with sorted columns. Journal of Computer and System Sciences, 24(4):197\u2013208, 1982.","journal-title":"Journal of Computer and System Sciences"},{"issue":"3","key":"8_CR10","doi-asserted-by":"publisher","first-page":"411","DOI":"10.1016\/0196-6774(88)90031-4","volume":"9","author":"H. N. Gabow","year":"1988","unstructured":"H. N. Gabow and R. E. Tarjan. Algorithms for two bottleneck optimization problems. Journal of Algorithms, 9(3):411\u2013417, 1988.","journal-title":"Journal of Algorithms"},{"issue":"4","key":"8_CR11","doi-asserted-by":"publisher","first-page":"628","DOI":"10.1137\/0216043","volume":"16","author":"D. S. Hirschberg","year":"1987","unstructured":"D. S. Hirschberg and L. L. Larmore. The least weight subsequence problem. SIAM Journal on Computing, 16(4):628\u2013638, 1987.","journal-title":"SIAM Journal on Computing"},{"key":"8_CR12","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1016\/0020-0190(87)90154-2","volume":"24","author":"D. S. Hirschberg","year":"1987","unstructured":"D. S. Hirschberg and D. J. Volper. Improved update\/query algorithms for the interval valuation problem. Information Processing Letters, 24:307\u2013310, 1987.","journal-title":"Information Processing Letters"},{"key":"8_CR13","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1090\/pspum\/007\/0157778","volume":"7","author":"A.J. Hoffman","year":"1961","unstructured":"A.J. Hoffman. On simple linear programming problems. In Convexity, Proc. Symposia in Pure Mathematics, volume 7, pages 317\u2013327, Providence, RI, 1961. American Mathematical Society.","journal-title":"Convexity, Proc. Symposia in Pure Mathematics"},{"key":"8_CR14","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1016\/0166-218X(94)00019-A","volume":"63","author":"B. Klinz","year":"1995","unstructured":"B. Klinz, R. Rudolf, and G.J. Woeginger. On the recognition of bottleneck monge matrices. Discrete Applied Mathematics, 63:43\u201374, 1995.","journal-title":"Discrete Applied Mathematics"},{"issue":"3","key":"8_CR15","doi-asserted-by":"publisher","first-page":"490","DOI":"10.1016\/0196-6774(91)90016-R","volume":"12","author":"L. L. Larmore","year":"1991","unstructured":"L. L. Larmore and B. Schieber. On-line dynamic programming with applications to the prediction of RNA secondary structure. Journal of Algorithms, 12(3):490\u2013515, 1991.","journal-title":"Journal of Algorithms"},{"key":"8_CR16","unstructured":"E. Seiffart. Algebraic transportation and assignment problems with \u201cMonge-property\u201d and \u201cquasi-convexity\u201d. Discrete Applied Mathematics, 1993."},{"key":"8_CR17","first-page":"418","volume-title":"Journal of Algorithms","author":"R. Wilber","year":"1988","unstructured":"R. Wilber. The concave least-weight subsequence problem revisited. Journal of Algorithms, 9 3):418\u2013425, 1988."}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2002"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45687-2_8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,23]],"date-time":"2023-01-23T20:29:29Z","timestamp":1674505769000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/3-540-45687-2_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002]]},"ISBN":["9783540440406","9783540456872"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/3-540-45687-2_8","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2002]]},"assertion":[{"value":"4 October 2002","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}