{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,22]],"date-time":"2025-03-22T07:10:21Z","timestamp":1742627421521,"version":"3.40.2"},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642283314"},{"type":"electronic","value":"9783642283321"}],"license":[{"start":{"date-parts":[[2012,1,1]],"date-time":"2012-01-01T00:00:00Z","timestamp":1325376000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-28332-1_12","type":"book-chapter","created":{"date-parts":[[2012,2,29]],"date-time":"2012-02-29T14:45:36Z","timestamp":1330526736000},"page":"131-142","source":"Crossref","is-referenced-by-count":4,"title":["Fast and Cache-Oblivious Dynamic Programming with Local Dependencies"],"prefix":"10.1007","author":[{"given":"Philip","family":"Bille","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Morten","family":"St\u00f6ckel","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"9","key":"12_CR1","doi-asserted-by":"publisher","first-page":"1116","DOI":"10.1145\/48529.48535","volume":"31","author":"A. Aggarwal","year":"1988","unstructured":"Aggarwal, A., Vitter, J.S.: The Input\/Output complexity of sorting and related problems. Commun. ACM\u00a031(9), 1116\u20131127 (1988)","journal-title":"Commun. ACM"},{"key":"12_CR2","doi-asserted-by":"crossref","unstructured":"Bille, P.: Faster approximate string matching for short patterns. Theory Comput. Syst. (2011) (to appear)","DOI":"10.1007\/s00224-011-9322-y"},{"issue":"3","key":"12_CR3","doi-asserted-by":"publisher","first-page":"486","DOI":"10.1016\/j.tcs.2008.08.042","volume":"409","author":"P. Bille","year":"2008","unstructured":"Bille, P., Farach-Colton, M.: Fast and compact regular expression matching. Theoret. Comput. Sci.\u00a0409(3), 486\u2013496 (2008)","journal-title":"Theoret. Comput. Sci."},{"key":"12_CR4","doi-asserted-by":"crossref","unstructured":"Chowdhury, R.A., Ramachandran, V.: Cache-oblivious dynamic programming. In: Proc. 17th Symp. on Discrete Algorithms, pp. 591\u2013600 (2006)","DOI":"10.1145\/1109557.1109622"},{"key":"12_CR5","unstructured":"Chowdhury, R.A., Ramachandran, V.: Cache-efficient dynamic programming algorithms for multicores. In: Proc. 20th Symp. on Parallelism in Algorithms and Architectures, pp. 207\u2013216 (2008), http:\/\/doi.acm.org\/10.1145\/1378533.1378574"},{"key":"12_CR6","doi-asserted-by":"publisher","first-page":"495","DOI":"10.1109\/TCBB.2008.94","volume":"7","author":"R.A. Chowdhury","year":"2010","unstructured":"Chowdhury, R.A., Le, H.S., Ramachandran, V.: Cache-oblivious dynamic programming for bioinformatics. Trans. Comput. Biol. and Bioinformatics\u00a07, 495\u2013510 (2010)","journal-title":"Trans. Comput. Biol. and Bioinformatics"},{"issue":"6","key":"12_CR7","doi-asserted-by":"publisher","first-page":"1761","DOI":"10.1137\/S0097539700370527","volume":"31","author":"R. Cole","year":"2002","unstructured":"Cole, R., Hariharan, R.: Approximate string matching: A simpler faster algorithm. SIAM J. Comput.\u00a031(6), 1761\u20131782 (2002)","journal-title":"SIAM J. Comput."},{"issue":"6","key":"12_CR8","doi-asserted-by":"publisher","first-page":"1654","DOI":"10.1137\/S0097539702402007","volume":"32","author":"M. Crochemore","year":"2003","unstructured":"Crochemore, M., Landau, G.M., Ziv-Ukelson, M.: A subquadratic sequence alignment algorithm for unrestricted scoring matrices. SIAM J. Comput.\u00a032(6), 1654\u20131673 (2003)","journal-title":"SIAM J. Comput."},{"key":"12_CR9","doi-asserted-by":"crossref","unstructured":"Driga, A., Lu, P., Schaeffer, J., Szafron, D., Charter, K., Parsons, I.: FastLSA: A fast, linear-space, parallel and sequential algorithm for sequence alignment. In: Proc. Intl. Conf. on Parallel Processing, pp. 48\u201357 (2005)","DOI":"10.1109\/ICPP.2003.1240565"},{"key":"12_CR10","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1007\/s00453-006-1217-y","volume":"45","author":"A. Driga","year":"2006","unstructured":"Driga, A., Lu, P., Schaeffer, J., Szafron, D., Charter, K., Parsons, I.: FastLSA: A fast, linear-space, parallel and sequential algorithm for sequence alignment. Algorithmica\u00a045, 337\u2013375 (2006)","journal-title":"Algorithmica"},{"key":"12_CR11","doi-asserted-by":"crossref","unstructured":"Frigo, M., Leiserson, C.E., Prokop, H., Ramachandran, S.: Cache-oblivious algorithms. In: Proc. 40th Symp. Foundations of Computer Science, pp. 285\u2013297 (1999)","DOI":"10.1109\/SFFCS.1999.814600"},{"key":"12_CR12","doi-asserted-by":"crossref","unstructured":"Gusfield, D.: Algorithms on strings, trees, and sequences: computer science and computational biology, Cambridge (1997)","DOI":"10.1017\/CBO9780511574931"},{"key":"12_CR13","unstructured":"Hermelin, D., Landau, G.M., Landau, S., Weimann, O.: A unified algorithm for accelerating edit-distance computation via text-compression. In: Proc. 26th Symp. Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), vol.\u00a03, pp. 529\u2013540 (2009)"},{"issue":"6","key":"12_CR14","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1145\/360825.360861","volume":"18","author":"D.S. Hirschberg","year":"1975","unstructured":"Hirschberg, D.S.: A linear space algorithm for computing maximal common subsequences. Commun. ACM\u00a018(6), 341\u2013343 (1975)","journal-title":"Commun. ACM"},{"key":"12_CR15","doi-asserted-by":"publisher","first-page":"350","DOI":"10.1145\/359581.359603","volume":"20","author":"J.W. Hunt","year":"1977","unstructured":"Hunt, J.W., Szymanski, T.G.: A fast algorithm for computing longest common subsequences. Commun. ACM\u00a020, 350\u2013353 (1977)","journal-title":"Commun. ACM"},{"key":"12_CR16","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1016\/0196-6774(89)90010-2","volume":"10","author":"G.M. Landau","year":"1989","unstructured":"Landau, G.M., Vishkin, U.: Fast parallel and serial approximate string matching. J. Algorithms\u00a010, 157\u2013169 (1989)","journal-title":"J. Algorithms"},{"key":"12_CR17","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1016\/0022-0000(80)90002-1","volume":"20","author":"W. Masek","year":"1980","unstructured":"Masek, W., Paterson, M.: A faster algorithm for computing string edit distances. J. Comput. System Sci.\u00a020, 18\u201331 (1980)","journal-title":"J. Comput. System Sci."},{"issue":"1","key":"12_CR18","first-page":"11","volume":"4","author":"E.W. Myers","year":"1988","unstructured":"Myers, E.W., Miller, W.: Optimal alignments in linear space. Comput. Appl. Biosci.\u00a04(1), 11\u201317 (1988)","journal-title":"Comput. Appl. Biosci."},{"issue":"3","key":"12_CR19","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1145\/316542.316550","volume":"46","author":"G. Myers","year":"1999","unstructured":"Myers, G.: A fast bit-vector algorithm for approximate string matching based on dynamic programming. J. ACM\u00a046(3), 395\u2013415 (1999)","journal-title":"J. ACM"},{"issue":"1","key":"12_CR20","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1145\/375360.375365","volume":"33","author":"G. Navarro","year":"2001","unstructured":"Navarro, G.: A guided tour to approximate string matching. ACM Comput. Surv.\u00a033(1), 31\u201388 (2001)","journal-title":"ACM Comput. Surv."},{"key":"12_CR21","doi-asserted-by":"publisher","first-page":"168","DOI":"10.1145\/321796.321811","volume":"21","author":"R.A. Wagner","year":"1974","unstructured":"Wagner, R.A., Fischer, M.J.: The string-to-string correction problem. J. ACM\u00a021, 168\u2013173 (1974)","journal-title":"J. ACM"}],"container-title":["Lecture Notes in Computer Science","Language and Automata Theory and Applications"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-28332-1_12","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,22]],"date-time":"2025-03-22T06:19:32Z","timestamp":1742624372000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-28332-1_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642283314","9783642283321"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-28332-1_12","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}