{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:57:28Z","timestamp":1725663448842},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540549673"},{"type":"electronic","value":"9783540466123"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1991]]},"DOI":"10.1007\/3-540-54967-6_80","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T23:22:00Z","timestamp":1330212120000},"page":"347-359","source":"Crossref","is-referenced-by-count":0,"title":["Improved selection in totally monotone arrays"],"prefix":"10.1007","author":[{"given":"Yishay","family":"Mansour","sequence":"first","affiliation":[]},{"given":"James K.","family":"Park","sequence":"additional","affiliation":[]},{"given":"Baruch","family":"Schieber","sequence":"additional","affiliation":[]},{"given":"Sandeep","family":"Sen","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,31]]},"reference":[{"issue":"5","key":"24_CR1","doi-asserted-by":"publisher","first-page":"968","DOI":"10.1137\/0219066","volume":"19","author":"A. Apostolico","year":"1990","unstructured":"A. Apostolico, M. J. Atallah, L. L. Larmore, and H. S. McFaddin. Efficient parallel algorithms for string editing and related problems. SIAM Journal on Computing, 19(5):968\u2013988, 1990.","journal-title":"SIAM Journal on Computing"},{"key":"24_CR2","doi-asserted-by":"crossref","unstructured":"M. J. Atallah and S. R. Kosaraju. An efficient parallel algorithm for the row minima of a totally monotone matrix. In Proceedings of the 2nd Annual ACM-SIAM Symposium on Discrete Algorithms, pages 394\u2013403, 1991. Submitted to Journal of Algorithms.","DOI":"10.1016\/0196-6774(92)90046-F"},{"key":"24_CR3","doi-asserted-by":"crossref","unstructured":"M. J. Atallah, S. R. Kosaraju, L. L. Larmore, G. Miller, and S. Teng. Constructing trees in parallel. In Proceedings of the 1st Annual ACM Symposium on Parallel Algorithms and Architectures, pages 421\u2013431, 1989.","DOI":"10.1145\/72935.72980"},{"issue":"2","key":"24_CR4","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":"24_CR5","doi-asserted-by":"crossref","unstructured":"A. Aggarwal, D. Kravets, J. K. Park, and S. Sen. Parallel searching in generalized Monge arrays with applications. In Proceedings of the 2nd Annual ACM Symposium on Parallel Algorithms and Architectures, pages 259\u2013268, 1990.","DOI":"10.1145\/97444.97693"},{"key":"24_CR6","doi-asserted-by":"crossref","unstructured":"A. Aggarwal and J. K. Park. Parallel searching in multidimensional monotone arrays. Research Report RC 14826, IBM T. J. Watson Research Center, August 1989. Submitted to Journal of Algorithms. Portions of this paper appear in Proceedings of the 29th Annual IEEE Symposium on Foundations of Computer Science, pages 497\u2013512, 1988.","DOI":"10.1109\/SFCS.1988.21966"},{"key":"24_CR7","doi-asserted-by":"crossref","unstructured":"A. Aggarwal and J. K. Park. Sequential searching in multidimensional monotone arrays. Research Report RC 15128, IBM T. J. Watson Research Center, November 1989. Submitted to Journal of Algorithms. Portions of this paper appear in Proceedings of the 29th Annual IEEE Symposium on Foundations of Computer Science, pages 497\u2013512, 1988.","DOI":"10.1109\/SFCS.1988.21966"},{"key":"24_CR8","unstructured":"A. Aggarwal and J. K. Park. Improved algorithms for economic lot-size problems. Operations Research, 1991. To appear. An earlier version of this paper appears as Research Report RC 15626, IBM T. J. Watson Research Center, March 1990."},{"key":"24_CR9","first-page":"192","volume-title":"A faster parallel algorithm for a matrix searching problem","author":"M. J. Atallah","year":"1990","unstructured":"M. J. Atallah. A faster parallel algorithm for a matrix searching problem. In G. Goos and J. Hartmanis, editors, Proceedings of the 2nd Scandinavian Workshop on Algorithm Theory, pages 192\u2013200, New York, NY, 1990. Springer-Verlag. Submitted to Algorithmica."},{"issue":"4","key":"24_CR10","doi-asserted-by":"crossref","first-page":"448","DOI":"10.1016\/S0022-0000(73)80033-9","volume":"7","author":"M. Blum","year":"1973","unstructured":"M. Blum, R. W. Floyd, V. Pratt, R. L. Rivest, and R. E. Tarjan. Time bounds for selection. Journal of Computer and System Sciences, 7(4):448\u2013461, 1973.","journal-title":"Journal of Computer and System Sciences"},{"issue":"1","key":"24_CR11","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/0196-6774(90)90031-9","volume":"11","author":"D. Eppstein","year":"1990","unstructured":"D. Eppstein. Sequence comparison with mixed convex and concave costs. Journal of Algorithms, 11(1):85\u2013101, 1990.","journal-title":"Journal of Algorithms"},{"issue":"6","key":"24_CR12","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1016\/0020-0190(90)90215-J","volume":"33","author":"Z. Galil","year":"1990","unstructured":"Z. Galil and K. Park. A linear-time algorithm for concave one-dimensional dynamic programming. Information Processing Letters, 33(6):309\u2013311, 1990.","journal-title":"Information Processing Letters"},{"key":"24_CR13","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1090\/pspum\/007\/0157778","volume-title":"Convexity: Proceedings of the Seventh Symposium in Pure Mathematics of the AMS, volume 7 of Proceedings of Symposia in Pure Mathematics","author":"A. J. Hoffman","year":"1963","unstructured":"A. J. Hoffman. On simple linear programming problems. In V. Klee, editor, Convexity: Proceedings of the Seventh Symposium in Pure Mathematics of the AMS, volume 7 of Proceedings of Symposia in Pure Mathematics, pages 317\u2013327. American Mathematical Society, Providence, RI, 1963."},{"issue":"1","key":"24_CR14","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1137\/0403009","volume":"3","author":"M. M. Klawe","year":"1990","unstructured":"M. M. Klawe and D. J. Kleitman. An almost linear time algorithm for generalized matrix searching. SIAM Journal on Discrete Mathematics, 3(1):81\u201397, 1990.","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"24_CR15","volume-title":"Technical Report 89-16","author":"M. M. Klawe","year":"1989","unstructured":"M. M. Klawe. A simple linear time algorithm for concave one-dimensional dynamic programming. Technical Report 89-16, University of British Columbia, Vancouver, 1989."},{"key":"24_CR16","doi-asserted-by":"crossref","unstructured":"D. Kravets and J. K. Park. Selection and sorting in totally monotone arrays. Mathematical Systems Theory, 1991. To appear. An earlier version of this paper appears in Proceedings of the 1st Annual ACM-SIAM Symposium on Discrete Algorithms, pages 494\u2013502, 1990.","DOI":"10.1007\/BF02090398"},{"key":"24_CR17","unstructured":"L. L. Larmore and B. Schieber. On-line dynamic programming with applications to the prediction of RNA secondary structure. Journal of Algorithms, 1991. To appear. An earlier version of this paper appears in Proceedings of the 1st Annual ACM-SIAM Symposium on Discrete Algorithms, pages 503\u2013512, 1990."},{"issue":"3","key":"24_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. Journal of Algorithms, 9(3):418\u2013425, 1988.","journal-title":"Journal of Algorithms"}],"container-title":["Lecture Notes in Computer Science","Foundations of Software Technology and Theoretical Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-54967-6_80.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T20:57:05Z","timestamp":1605646625000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-54967-6_80"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1991]]},"ISBN":["9783540549673","9783540466123"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/3-540-54967-6_80","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1991]]}}}