{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,13]],"date-time":"2025-05-13T18:40:05Z","timestamp":1747161605093,"version":"3.40.5"},"publisher-location":"Cham","reference-count":22,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319126906"},{"type":"electronic","value":"9783319126913"}],"license":[{"start":{"date-parts":[[2014,1,1]],"date-time":"2014-01-01T00:00:00Z","timestamp":1388534400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2014,1,1]],"date-time":"2014-01-01T00:00:00Z","timestamp":1388534400000},"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":[[2014]]},"DOI":"10.1007\/978-3-319-12691-3_48","type":"book-chapter","created":{"date-parts":[[2014,11,14]],"date-time":"2014-11-14T21:11:32Z","timestamp":1415999492000},"page":"637-651","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Parameterized and Subexponential-Time Complexity of Satisfiability Problems and Applications"],"prefix":"10.1007","author":[{"given":"Iyad","family":"Kanj","sequence":"first","affiliation":[]},{"given":"Stefan","family":"Szeider","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2014,11,13]]},"reference":[{"key":"48_CR1","doi-asserted-by":"publisher","first-page":"461","DOI":"10.1007\/s00453-001-0116-5","volume":"33","author":"J Alber","year":"2002","unstructured":"Alber, J., Bodlaender, H., Ferneau, H., Niedermeier, R.: Fixed parameter algorithms for dominating set and related problems on planar graphs. Algorithmica 33, 461\u2013493 (2002)","journal-title":"Algorithmica"},{"key":"48_CR2","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1016\/j.tcs.2004.08.002","volume":"329","author":"T Br\u00fcggemann","year":"2004","unstructured":"Br\u00fcggemann, T., Kern, W.: An improved deterministic local search algorithm for 3SAT. Theoret. Comput. Sci. 329, 303\u2013313 (2004)","journal-title":"Theoret. Comput. Sci."},{"issue":"4","key":"48_CR3","doi-asserted-by":"publisher","first-page":"789","DOI":"10.1016\/S0022-0000(03)00074-6","volume":"67","author":"L Cai","year":"2003","unstructured":"Cai, L., Juedes, D.: On the existence of subexponential parameterized algorithms. J. Comput. Syst. Sci. 67(4), 789\u2013807 (2003)","journal-title":"J. Comput. Syst. Sci."},{"key":"48_CR4","doi-asserted-by":"crossref","unstructured":"Calabro, C., Impagliazzo, R., Paturi, R.: A duality between clause width and clause density for SAT. In: IEEE Conference on Computational Complexity, pp. 252\u2013260 (2006)","DOI":"10.1109\/CCC.2006.6"},{"issue":"2","key":"48_CR5","doi-asserted-by":"publisher","first-page":"216","DOI":"10.1016\/j.ic.2005.05.001","volume":"201","author":"J Chen","year":"2005","unstructured":"Chen, J., Chor, B., Fellows, M., Huang, X., Juedes, D., Kanj, I., Xia, G.: Tight lower bounds for certain parameterized NP-hard problems. Inf. Comput. 201(2), 216\u2013231 (2005)","journal-title":"Inf. Comput."},{"issue":"8","key":"48_CR6","doi-asserted-by":"publisher","first-page":"1346","DOI":"10.1016\/j.jcss.2006.04.007","volume":"72","author":"J Chen","year":"2006","unstructured":"Chen, J., Huang, X., Kanj, I., Xia, G.: Strong computational lower bounds via parameterized complexity. J. Comput. Syst. Sci. 72(8), 1346\u20131367 (2006)","journal-title":"J. Comput. Syst. Sci."},{"key":"48_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"162","DOI":"10.1007\/978-3-642-30891-8_11","volume-title":"The Multivariate Algorithmic Revolution and Beyond","author":"J Chen","year":"2012","unstructured":"Chen, J., Kanj, I.A.: Parameterized complexity and subexponential-time computability. In: Bodlaender, H.L., Downey, R., Fomin, F.V., Marx, D. (eds.) Fellows Festschrift 2012. LNCS, vol. 7370, pp. 162\u2013195. Springer, Heidelberg (2012)"},{"issue":"27\u201329","key":"48_CR8","doi-asserted-by":"publisher","first-page":"2641","DOI":"10.1016\/j.tcs.2009.03.006","volume":"410","author":"J Chen","year":"2009","unstructured":"Chen, J., Kanj, I., Xia, G.: On parameterized exponential time complexity. Theoret. Comput. Sci. 410(27\u201329), 2641\u20132648 (2009)","journal-title":"Theoret. Comput. Sci."},{"issue":"3","key":"48_CR9","doi-asserted-by":"publisher","first-page":"314","DOI":"10.1016\/j.tcs.2005.10.003","volume":"351","author":"Y Chen","year":"2006","unstructured":"Chen, Y., Flum, J.: On miniaturized problems in parameterized complexity theory. Theoret. Comput. Sci. 351(3), 314\u2013336 (2006)","journal-title":"Theoret. Comput. Sci."},{"issue":"1","key":"48_CR10","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1093\/logcom\/exn029","volume":"19","author":"Y Chen","year":"2009","unstructured":"Chen, Y., Flum, J.: Subexponential time and fixed-parameter tractability: exploiting the miniaturization mapping. J. Logic Comput. 19(1), 89\u2013122 (2009)","journal-title":"J. Logic Comput."},{"issue":"4","key":"48_CR11","doi-asserted-by":"publisher","first-page":"1228","DOI":"10.1137\/070687153","volume":"37","author":"Y Chen","year":"2007","unstructured":"Chen, Y., Grohe, M.: An isomorphism between subexponential and parameterized complexity theory. SIAM J. Comput. 37(4), 1228\u20131258 (2007)","journal-title":"SIAM J. Comput."},{"key":"48_CR12","doi-asserted-by":"crossref","unstructured":"Cygan, M., Dell, H., Lokshtanov, D., Marx, D., Nederlof, J., Okamoto, Y., Paturi, R., Saurabh, S., Wahlstr\u00f6m, M.: On problems as hard as CNF-SAT. In: IEEE Conference on Computational Complexity, pp. 74\u201384. IEEE (2012)","DOI":"10.1109\/CCC.2012.36"},{"key":"48_CR13","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-5559-1","volume-title":"Fundamentals of Parameterized Complexity","author":"R Downey","year":"2013","unstructured":"Downey, R., Fellows, M.: Fundamentals of Parameterized Complexity. Springer, New York (2013)"},{"key":"48_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"142","DOI":"10.1007\/11847250_13","volume-title":"Parameterized and Exact Computation","author":"H Fernau","year":"2006","unstructured":"Fernau, H.: edge dominating set: efficient enumeration-based exact algorithms. In: Bodlaender, H.L., Langston, M.A. (eds.) IWPEC 2006. LNCS, vol. 4169, pp. 142\u2013153. Springer, Heidelberg (2006)"},{"key":"48_CR15","series-title":"An EATCS Series","volume-title":"Texts in Theoretical Computer Science","author":"J Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized complexity theory. In: Brauer, W., Rozenberg, G., Salomaa, A. (eds.) Texts in Theoretical Computer Science. An EATCS Series, vol. XIV. Springer, Berlin (2006)"},{"key":"48_CR16","volume-title":"Parameterized Complexity Theory","author":"J Fl\u00fcm","year":"2010","unstructured":"Fl\u00fcm, J., Grohe, M.: Parameterized Complexity Theory. Springer-verlag, Berlin (2010)"},{"issue":"2","key":"48_CR17","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1006\/jcss.2000.1727","volume":"62","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R.: On the complexity of $$k$$-SAT. J. Comput. Syst. Sci. 62(2), 367\u2013375 (2001)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"48_CR18","doi-asserted-by":"publisher","first-page":"512","DOI":"10.1006\/jcss.2001.1774","volume":"63","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? J. Comput. Syst. Sci. 63(4), 512\u2013530 (2001)","journal-title":"J. Comput. Syst. Sci."},{"key":"48_CR19","doi-asserted-by":"crossref","unstructured":"Lokshtanov, D., Marx, D., Saurabh, S.: Slightly superexponential parameterized problems. In: Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 760\u2013776 (2011)","DOI":"10.1137\/1.9781611973082.60"},{"key":"48_CR20","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"C Papadimitriou","year":"1991","unstructured":"Papadimitriou, C., Yannakakis, M.: Optimization, approximation, and complexity classes. J. Comput. Syst. Sci. 43, 425\u2013440 (1991)","journal-title":"J. Comput. Syst. Sci."},{"key":"48_CR21","doi-asserted-by":"crossref","unstructured":"Patrascu, M., Williams, R.: On the possibility of faster SAT algorithms. In: Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1065\u20131075 (2010)","DOI":"10.1137\/1.9781611973075.86"},{"issue":"1","key":"48_CR22","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1016\/j.disopt.2010.07.003","volume":"8","author":"S Szeider","year":"2011","unstructured":"Szeider, S.: The parameterized complexity of $$k$$-flip local search for SAT and MAX SAT. Discrete Optim. 8(1), 139\u2013145 (2011)","journal-title":"Discrete Optim."}],"container-title":["Lecture Notes in Computer Science","Combinatorial Optimization and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-12691-3_48","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,13]],"date-time":"2025-05-13T18:25:56Z","timestamp":1747160756000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-12691-3_48"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319126906","9783319126913"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-12691-3_48","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]},"assertion":[{"value":"13 November 2014","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}