{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:23:09Z","timestamp":1759638189995},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642325885"},{"type":"electronic","value":"9783642325892"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-32589-2_62","type":"book-chapter","created":{"date-parts":[[2012,8,1]],"date-time":"2012-08-01T04:44:32Z","timestamp":1343796272000},"page":"718-727","source":"Crossref","is-referenced-by-count":7,"title":["Reducing a Target Interval to a Few Exact Queries"],"prefix":"10.1007","author":[{"given":"Jesper","family":"Nederlof","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Erik Jan","family":"van Leeuwen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ruben","family":"van der Zwaan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"3","key":"62_CR1","doi-asserted-by":"publisher","first-page":"306","DOI":"10.1016\/j.jcss.2004.04.004","volume":"69","author":"R. Beier","year":"2004","unstructured":"Beier, R., V\u00f6cking, B.: Random knapsack in expected polynomial time. J. Comput. Syst. Sci.\u00a069(3), 306\u2013329 (2004)","journal-title":"J. Comput. Syst. Sci."},{"key":"62_CR2","unstructured":"Bellman, R.E.: Dynamic Programming (reprint 2003). Dover Publications, Incorporated (1954)"},{"key":"62_CR3","doi-asserted-by":"crossref","unstructured":"Bj\u00f6rklund, A.: Determinant sums for undirected Hamiltonicity. In: FOCS, pp. 173\u2013182. IEEE Computer Society (2010)","DOI":"10.1109\/FOCS.2010.24"},{"key":"62_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1007\/978-3-642-11269-0_2","volume-title":"Parameterized and Exact Computation","author":"H.L. Bodlaender","year":"2009","unstructured":"Bodlaender, H.L.: Kernelization: New Upper and Lower Bound Techniques. In: Chen, J., Fomin, F.V. (eds.) IWPEC 2009. LNCS, vol.\u00a05917, pp. 17\u201337. Springer, Heidelberg (2009)"},{"issue":"8","key":"62_CR5","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1016\/j.jcss.2009.04.001","volume":"75","author":"H.L. Bodlaender","year":"2009","unstructured":"Bodlaender, H.L., Downey, R.G., Fellows, M.R., Hermelin, D.: On problems without polynomial kernels. J. Comput. Syst. Sci.\u00a075(8), 423\u2013434 (2009)","journal-title":"J. Comput. Syst. Sci."},{"key":"62_CR6","series-title":"LIPIcs","first-page":"421","volume-title":"STACS","author":"H. Fernau","year":"2009","unstructured":"Fernau, H., Fomin, F.V., Lokshtanov, D., Raible, D., Saurabh, S., Villanger, Y.: Kernel(s) for problems with no kernel: On out-trees with many leaves. In: Albers, S., Marion, J.-Y. (eds.) STACS. LIPIcs, vol.\u00a03, pp. 421\u2013432. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany (2009)"},{"key":"62_CR7","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-16533-7","volume-title":"Exact Exponential Algorithms","author":"F.V. Fomin","year":"2010","unstructured":"Fomin, F.V., Kratsch, D.: Exact Exponential Algorithms, 1st edn. Springer, New York (2010)","edition":"1"},{"issue":"5","key":"62_CR8","doi-asserted-by":"publisher","first-page":"1667","DOI":"10.1137\/060668092","volume":"39","author":"D. Harnik","year":"2010","unstructured":"Harnik, D., Naor, M.: On the compressibility of np instances and cryptographic applications. SIAM J. Comput.\u00a039(5), 1667\u20131713 (2010)","journal-title":"SIAM J. Comput."},{"key":"62_CR9","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1145\/321906.321909","volume":"22","author":"O. Ibarra","year":"1975","unstructured":"Ibarra, O., Kim, C.: Fast approximation algorithms for the knapsack and sum of subset problems. Journal of the ACM\u00a022, 463\u2013468 (1975)","journal-title":"Journal of the ACM"},{"key":"62_CR10","doi-asserted-by":"crossref","unstructured":"Kaski, P., Koivisto, M., Nederlof, J.: Homomorphic hashing for sparse coefficient extraction. Manuscript (2012)","DOI":"10.1007\/978-3-642-33293-7_15"},{"key":"62_CR11","doi-asserted-by":"crossref","unstructured":"Lokshtanov, D., Nederlof, J.: Saving space by algebraization. In: Schulman, L.J. (ed.) STOC, pp. 321\u2013330. ACM (2010)","DOI":"10.1145\/1806689.1806735"},{"issue":"2","key":"62_CR12","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1137\/S0097539792239291","volume":"24","author":"Y. Mansour","year":"1995","unstructured":"Mansour, Y.: Randomized interpolation and approximation of sparse polynomials. SIAM J. Comput.\u00a024(2), 357\u2013368 (1995)","journal-title":"SIAM J. Comput."},{"key":"62_CR13","unstructured":"Nederlof, J.: Space and Time Efficient Structural Improvements of Dynamic Programming Algorithms. PhD thesis, University of Bergen (2011)"},{"issue":"9","key":"62_CR14","doi-asserted-by":"publisher","first-page":"494","DOI":"10.1287\/mnsc.15.9.494","volume":"15","author":"G.L. Nemhauser","year":"1969","unstructured":"Nemhauser, G.L., Ullmann, Z.: Discrete dynamic programming and capital allocation. Management Science\u00a015(9), 494\u2013505 (1969)","journal-title":"Management Science"},{"issue":"3","key":"62_CR15","doi-asserted-by":"publisher","first-page":"456","DOI":"10.1137\/0210033","volume":"10","author":"R. Schroeppel","year":"1981","unstructured":"Schroeppel, R., Shamir, A.: A T\u2009=\u2009O(2\n                  n\/2), S\u2009=\u2009O(2\n                  n\/4) algorithm for certain NP-complete problems. SIAM J. Comput.\u00a010(3), 456\u2013464 (1981)","journal-title":"SIAM J. Comput."},{"issue":"10","key":"62_CR16","doi-asserted-by":"publisher","first-page":"76","DOI":"10.1145\/1562764.1562785","volume":"52","author":"D.A. Spielman","year":"2009","unstructured":"Spielman, D.A., Teng, S.-H.: Smoothed analysis: an attempt to explain the behavior of algorithms in practice. Commun. ACM\u00a052(10), 76\u201384 (2009)","journal-title":"Commun. ACM"},{"issue":"3","key":"62_CR17","doi-asserted-by":"publisher","first-page":"397","DOI":"10.1016\/j.dam.2007.03.023","volume":"156","author":"G.J. Woeginger","year":"2008","unstructured":"Woeginger, G.J.: Open problems around exact algorithms. Discrete Applied Mathematics\u00a0156(3), 397\u2013405 (2008)","journal-title":"Discrete Applied Mathematics"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2012"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-32589-2_62","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,4]],"date-time":"2019-05-04T04:20:45Z","timestamp":1556943645000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-32589-2_62"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642325885","9783642325892"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-32589-2_62","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}