{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,25]],"date-time":"2026-04-25T04:41:58Z","timestamp":1777092118229,"version":"3.51.4"},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642316111","type":"print"},{"value":"9783642316128","type":"electronic"}],"license":[{"start":{"date-parts":[[2012,1,1]],"date-time":"2012-01-01T00:00:00Z","timestamp":1325376000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2012,1,1]],"date-time":"2012-01-01T00:00:00Z","timestamp":1325376000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-31612-8_27","type":"book-chapter","created":{"date-parts":[[2012,6,18]],"date-time":"2012-06-18T05:14:42Z","timestamp":1339996482000},"page":"355-368","source":"Crossref","is-referenced-by-count":0,"title":["Fixed-Parameter Tractability of Satisfying beyond the Number of Variables"],"prefix":"10.1007","author":[{"given":"Robert","family":"Crowston","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gregory","family":"Gutin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mark","family":"Jones","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Venkatesh","family":"Raman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Saket","family":"Saurabh","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Anders","family":"Yeo","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"4","key":"27_CR1","doi-asserted-by":"publisher","first-page":"844","DOI":"10.1145\/210332.210337","volume":"42","author":"N. Alon","year":"1995","unstructured":"Alon, N., Yuster, R., Zwick, U.: Color-coding. J. ACM\u00a042(4), 844\u2013856 (1995)","journal-title":"J. ACM"},{"issue":"8","key":"27_CR2","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. System Sci.\u00a075(8), 423\u2013434 (2009)","journal-title":"J. Comput. System Sci."},{"key":"27_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"635","DOI":"10.1007\/978-3-642-04128-0_57","volume-title":"Algorithms - ESA 2009","author":"H.L. Bodlaender","year":"2009","unstructured":"Bodlaender, H.L., Thomass\u00e9, S., Yeo, A.: Kernel Bounds for Disjoint Cycles and Disjoint Paths. In: Fiat, A., Sanders, P. (eds.) ESA 2009. LNCS, vol.\u00a05757, pp. 635\u2013646. Springer, Heidelberg (2009)"},{"key":"27_CR4","doi-asserted-by":"crossref","unstructured":"Crowston, R., Gutin, G., Jones, M., Yeo, A.: A New Lower Bound on the Maximum Number of Satisfied clauses in Max-SAT and its algorithmic applications. Algorithmica, doi:10.1007\/s00453-011-9550-1","DOI":"10.1007\/s00453-011-9550-1"},{"key":"27_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"378","DOI":"10.1007\/978-3-642-02927-1_32","volume-title":"Automata, Languages and Programming","author":"M. Dom","year":"2009","unstructured":"Dom, M., Lokshtanov, D., Saurabh, S.: Incompressibility through Colors and IDs. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009, Part I. LNCS, vol.\u00a05555, pp. 378\u2013389. Springer, Heidelberg (2009)"},{"key":"27_CR6","doi-asserted-by":"crossref","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer (1999)","DOI":"10.1007\/978-1-4612-0515-9"},{"issue":"1","key":"27_CR7","doi-asserted-by":"publisher","first-page":"503","DOI":"10.1016\/S0304-3975(01)00337-1","volume":"289","author":"H. Fleischner","year":"2002","unstructured":"Fleischner, H., Kullmann, O., Szeider, S.: Polynomial-time recognition of minimal unsatisfiable formulas with fixed clause-variable difference. Theor. Comput. Sci.\u00a0289(1), 503\u2013516 (2002)","journal-title":"Theor. Comput. Sci."},{"key":"27_CR8","unstructured":"Fleischner, H., Szeider, S.: Polynomial-time recognition of minimal unsatisfiable formulas with fixed clause-variable difference. Electronic Colloquium on Computational Complexity (ECCC)\u00a07(49) (2000)"},{"key":"27_CR9","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer (2006)"},{"issue":"41","key":"27_CR10","doi-asserted-by":"publisher","first-page":"5744","DOI":"10.1016\/j.tcs.2011.06.018","volume":"412","author":"G. Gutin","year":"2011","unstructured":"Gutin, G., Jones, M., Yeo, A.: Kernels for below-upper-bound parameterizations of the hitting set and directed dominating set problems. Theor. Comput. Sci.\u00a0412(41), 5744\u20135751 (2011)","journal-title":"Theor. Comput. Sci."},{"issue":"1-3","key":"27_CR11","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1016\/S0166-218X(00)00245-6","volume":"107","author":"H. Kleine B\u00fcning","year":"2000","unstructured":"Kleine B\u00fcning, H.: On subclasses of minimal unsatisfiable formulas. Discrete Applied Mathematics\u00a0107(1-3), 83\u201398 (2000)","journal-title":"Discrete Applied Mathematics"},{"key":"27_CR12","unstructured":"Kleine B\u00fcning, H., Kullmann, O.: Minimal Unsatisfiability and Autarkies. In: Handbook of Satisfiability, ch. 11, pp. 339\u2013401"},{"key":"27_CR13","doi-asserted-by":"crossref","unstructured":"Kullmann, O.: An application of matroid theory to the sat problem. In: IEEE Conference on Computational Complexity, pp. 116\u2013124 (2000)","DOI":"10.1109\/CCC.2000.856741"},{"key":"27_CR14","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1016\/S0166-218X(02)00406-7","volume":"130","author":"O. Kullmann","year":"2003","unstructured":"Kullmann, O.: Lean clause-sets: Generalizations of minimally unsatisfiable clause-sets. Discr. Appl. Math.\u00a0130, 209\u2013249 (2003)","journal-title":"Discr. Appl. Math."},{"key":"27_CR15","doi-asserted-by":"crossref","unstructured":"Lov\u00e1sz, L., Plummer, M.D.: Matching theory. AMS Chelsea Publ. (2009)","DOI":"10.1090\/chel\/367"},{"key":"27_CR16","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1016\/0166-218X(85)90050-2","volume":"10","author":"B. Monien","year":"1985","unstructured":"Monien, B., Speckenmeyer, E.: Solving satisfiability in less than 2n steps. Discr. Appl. Math.\u00a010, 287\u2013295 (1985)","journal-title":"Discr. Appl. Math."},{"issue":"1","key":"27_CR17","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1016\/0022-0000(88)90042-6","volume":"37","author":"C.H. Papadimitriou","year":"1988","unstructured":"Papadimitriou, C.H., Wolfe, D.: The complexity of facets resolved. J. Comput. Syst. Sci.\u00a037(1), 2\u201313 (1988)","journal-title":"J. Comput. Syst. Sci."},{"key":"27_CR18","doi-asserted-by":"crossref","unstructured":"Srinivasan, A.: Improved approximations of packing and covering problems. In: STOC 1995, pp. 268\u2013276 (1995)","DOI":"10.1145\/225058.225138"},{"issue":"4","key":"27_CR19","doi-asserted-by":"publisher","first-page":"656","DOI":"10.1016\/j.jcss.2004.04.009","volume":"69","author":"S. Szeider","year":"2004","unstructured":"Szeider, S.: Minimal unsatisfiable formulas with bounded clause-variable difference are fixed-parameter tractable. J. Comput. Syst. Sci.\u00a069(4), 656\u2013674 (2004)","journal-title":"J. Comput. Syst. Sci."}],"container-title":["Lecture Notes in Computer Science","Theory and Applications of Satisfiability Testing \u2014 SAT 2012"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-31612-8_27","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,25]],"date-time":"2026-04-25T04:08:36Z","timestamp":1777090116000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-642-31612-8_27"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642316111","9783642316128"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-31612-8_27","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012]]}}}