{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,16]],"date-time":"2025-10-16T06:48:46Z","timestamp":1760597326003},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540744559"},{"type":"electronic","value":"9783540744566"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-74456-6_40","type":"book-chapter","created":{"date-parts":[[2007,8,14]],"date-time":"2007-08-14T07:29:48Z","timestamp":1187076588000},"page":"442-453","source":"Crossref","is-referenced-by-count":10,"title":["A Linear Time Algorithm for the k Maximal Sums Problem"],"prefix":"10.1007","author":[{"given":"Gerth St\u00f8lting","family":"Brodal","sequence":"first","affiliation":[]},{"given":"Allan Gr\u00f8nlund","family":"J\u00f8rgensen","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"9","key":"40_CR1","doi-asserted-by":"publisher","first-page":"865","DOI":"10.1145\/358234.381162","volume":"27","author":"J. Bentley","year":"1984","unstructured":"Bentley, J.: Programming pearls: algorithm design techniques. Commun. ACM\u00a027(9), 865\u2013873 (1984)","journal-title":"Commun. ACM"},{"issue":"2","key":"40_CR2","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1145\/383891.383893","volume":"26","author":"T. Fukuda","year":"2001","unstructured":"Fukuda, T., Morimoto, Y., Morishita, S., Tokuyama, T.: Data mining with optimized two-dimensional association rules. ACM Trans. Database Syst.\u00a026(2), 179\u2013213 (2001)","journal-title":"ACM Trans. Database Syst."},{"issue":"10","key":"40_CR3","doi-asserted-by":"publisher","first-page":"1294","DOI":"10.1093\/bioinformatics\/btg135","volume":"19","author":"L. Allison","year":"2003","unstructured":"Allison, L.: Longest biased interval and longest non-negative sum interval. Bioinformatics\u00a019(10), 1294\u20131295 (2003)","journal-title":"Bioinformatics"},{"issue":"3","key":"40_CR4","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1016\/0167-6423(83)90015-1","volume":"2","author":"D. Gries","year":"1982","unstructured":"Gries, D.: A note on a standard strategy for developing loop invariants and loops. Sci. Comput. Program.\u00a02(3), 207\u2013214 (1982)","journal-title":"Sci. Comput. Program."},{"key":"40_CR5","first-page":"446","volume-title":"Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms","author":"H. Tamaki","year":"1998","unstructured":"Tamaki, H., Tokuyama, T.: Algorithms for the maximum subarray problem based on matrix multiplication. In: Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, pp. 446\u2013452. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA (1998)"},{"key":"40_CR6","doi-asserted-by":"crossref","unstructured":"Takaoka, T.: Efficient algorithms for the maximum subarray problem by distance matrix multiplication. Electr. Notes Theor. Comput. Sci.\u00a061 (2002)","DOI":"10.1016\/S1571-0661(04)00313-5"},{"issue":"4","key":"40_CR7","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1016\/0020-0190(92)90200-F","volume":"43","author":"T. Takaoka","year":"1992","unstructured":"Takaoka, T.: A new upper bound on the complexity of the all pairs shortest path problem. Inf. Process. Lett.\u00a043(4), 195\u2013199 (1992)","journal-title":"Inf. Process. Lett."},{"key":"40_CR8","first-page":"247","volume-title":"7th International Symposium on Parallel Architectures, Algorithms, and Networks (I-SPAN 2004)","author":"S.E. Bae","year":"2004","unstructured":"Bae, S.E., Takaoka, T.: Algorithms for the problem of k maximum sums and a vlsi algorithm for the k maximum subarrays problem. In: 7th International Symposium on Parallel Architectures, Algorithms, and Networks (I-SPAN 2004), Hong Kong, SAR, China, 10-12 May 2004, pp. 247\u2013253. IEEE Computer Society, Los Alamitos (2004)"},{"key":"40_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1007\/978-3-540-30551-4_14","volume-title":"Algorithms and Computation","author":"F. Bengtsson","year":"2004","unstructured":"Bengtsson, F., Chen, J.: Efficient algorithms for k maximum sums. In: Fleischer, R., Trippen, G. (eds.) ISAAC 2004. LNCS, vol.\u00a03341, pp. 137\u2013148. Springer, Heidelberg (2004)"},{"key":"40_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"621","DOI":"10.1007\/11533719_63","volume-title":"Computing and Combinatorics","author":"S.E. Bae","year":"2005","unstructured":"Bae, S.E., Takaoka, T.: Improved algorithms for the k-maximum subarray problem for small k. In: Wang, L. (ed.) COCOON 2005. LNCS, vol.\u00a03595, pp. 621\u2013631. Springer, Heidelberg (2005)"},{"issue":"3","key":"40_CR11","doi-asserted-by":"publisher","first-page":"358","DOI":"10.1093\/comjnl\/bxl007","volume":"49","author":"S.E. Bae","year":"2006","unstructured":"Bae, S.E., Takaoka, T.: Improved algorithms for the k-maximum subarray problem. Comput. J.\u00a049(3), 358\u2013374 (2006)","journal-title":"Comput. J."},{"key":"40_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"515","DOI":"10.1007\/11602613_52","volume-title":"Algorithms and Computation","author":"T.-C. Lin","year":"2005","unstructured":"Lin, T.-C., Lee, D.T.: Randomized algorithm for the sum selection problem. In: Deng, X., Du, D.-Z. (eds.) ISAAC 2005. LNCS, vol.\u00a03827, pp. 515\u2013523. Springer, Heidelberg (2005)"},{"issue":"1-3","key":"40_CR13","doi-asserted-by":"publisher","first-page":"162","DOI":"10.1016\/j.tcs.2006.06.007","volume":"362","author":"C.-H. Cheng","year":"2006","unstructured":"Cheng, C.-H., Chen, K.-Y., Tien, W.-C., Chao, K.-M.: Improved algorithms for the k maximum-sums problems. Theoretical Computer Science\u00a0362(1-3), 162\u2013170 (2006)","journal-title":"Theoretical Computer Science"},{"key":"40_CR14","unstructured":"Chao, K.M., Liu, H.F.: Personal communication (2007)"},{"issue":"2","key":"40_CR15","doi-asserted-by":"publisher","first-page":"652","DOI":"10.1137\/S0097539795290477","volume":"28","author":"D. Eppstein","year":"1999","unstructured":"Eppstein, D.: Finding the k shortest paths. SIAM J. Comput.\u00a028(2), 652\u2013673 (1999)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"40_CR16","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1006\/inco.1993.1030","volume":"104","author":"G.N. Frederickson","year":"1993","unstructured":"Frederickson, G.N.: An optimal algorithm for selection in a min-heap. Inf. Comput.\u00a0104(2), 197\u2013214 (1993)","journal-title":"Inf. Comput."},{"issue":"1","key":"40_CR17","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1016\/0022-0000(89)90034-2","volume":"38","author":"J.R. Driscoll","year":"1989","unstructured":"Driscoll, J.R., Sarnak, N., Sleator, D.D., Tarjan, R.E.: Making data structures persistent. Journal of Computer and System Sciences\u00a038(1), 86\u2013124 (1989)","journal-title":"Journal of Computer and System Sciences"},{"issue":"1","key":"40_CR18","doi-asserted-by":"publisher","first-page":"52","DOI":"10.1137\/0215004","volume":"15","author":"D.D. Sleator","year":"1986","unstructured":"Sleator, D.D., Tarjan, R.E.: Self adjusting heaps. SIAM J. Comput.\u00a015(1), 52\u201369 (1986)","journal-title":"SIAM J. Comput."},{"key":"40_CR19","unstructured":"Crane, C.A.: Linear lists and priority queues as balanced binary trees. Technical Report STAN-CS-72-259, Dept. of Computer Science, Stanford University (1972)"},{"key":"40_CR20","volume-title":"The art of computer programming, sorting and searching","author":"D.E. Knuth","year":"1998","unstructured":"Knuth, D.E.: The art of computer programming, sorting and searching, 2nd edn., vol.\u00a03. Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, USA (1998)","edition":"2"},{"issue":"4","key":"40_CR21","doi-asserted-by":"publisher","first-page":"448","DOI":"10.1016\/S0022-0000(73)80033-9","volume":"7","author":"M. Blum","year":"1973","unstructured":"Blum, M., Floyd, R.W., Pratt, V.R., Rivest, R.L., Tarjan, R.E.: Time bounds for selection. J. Comput. Syst. Sci.\u00a07(4), 448\u2013461 (1973)","journal-title":"J. Comput. Syst. Sci."},{"issue":"6","key":"40_CR22","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1145\/512274.512284","volume":"7","author":"J.W.J. Williams","year":"1964","unstructured":"Williams, J.W.J.: Algorithm 232: Heapsort. Communications of the ACM\u00a07(6), 347\u2013348 (1964)","journal-title":"Communications of the ACM"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2007"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-74456-6_40.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,8,21]],"date-time":"2021-08-21T18:10:28Z","timestamp":1629569428000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-74456-6_40"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540744559","9783540744566"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-74456-6_40","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[]}}