{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,8]],"date-time":"2026-05-08T06:06:03Z","timestamp":1778220363388,"version":"3.51.4"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2012,10,11]],"date-time":"2012-10-11T00:00:00Z","timestamp":1349913600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2014,3]]},"DOI":"10.1007\/s00453-012-9697-4","type":"journal-article","created":{"date-parts":[[2012,10,11]],"date-time":"2012-10-11T01:20:41Z","timestamp":1349918441000},"page":"739-757","source":"Crossref","is-referenced-by-count":5,"title":["Fixed-Parameter Tractability of Satisfying Beyond the Number of Variables"],"prefix":"10.1007","volume":"68","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","published-online":{"date-parts":[[2012,10,11]]},"reference":[{"key":"9697_CR1","doi-asserted-by":"crossref","first-page":"196","DOI":"10.1016\/0097-3165(86)90060-9","volume":"43","author":"R. Aharoni","year":"1986","unstructured":"Aharoni, R., Linial, N.: Minimal non-two-colorable hypergraphs and minimal unsatisfiable formulas. J. Comb. Theory, Ser. A 43, 196\u2013204 (1986)","journal-title":"J. Comb. Theory, Ser. A"},{"key":"9697_CR2","doi-asserted-by":"crossref","first-page":"638","DOI":"10.1007\/s00453-010-9428-7","volume":"61","author":"N. Alon","year":"2011","unstructured":"Alon, N., Gutin, G., Kim, E.J., Szeider, S., Yeo, A.: Solving MAX-r-SAT above a tight lower bound. Algorithmica 61, 638\u2013655 (2011)","journal-title":"Algorithmica"},{"issue":"4","key":"9697_CR3","doi-asserted-by":"crossref","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 42(4), 844\u2013856 (1995)","journal-title":"J. ACM"},{"issue":"8","key":"9697_CR4","doi-asserted-by":"crossref","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. 75(8), 423\u2013434 (2009)","journal-title":"J. Comput. Syst. Sci."},{"issue":"35","key":"9697_CR5","doi-asserted-by":"crossref","first-page":"4570","DOI":"10.1016\/j.tcs.2011.04.039","volume":"412","author":"H.L. Bodlaender","year":"2011","unstructured":"Bodlaender, H.L., Thomasse, S., Yeo, A.: Kernel bounds for disjoint cycles and disjoint paths. Theor. Comput. Sci. 412(35), 4570\u20134578 (2011)","journal-title":"Theor. Comput. Sci."},{"key":"9697_CR6","doi-asserted-by":"crossref","first-page":"56","DOI":"10.1007\/s00453-011-9550-1","volume":"64","author":"R. Crowston","year":"2012","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 64, 56\u201368 (2012)","journal-title":"Algorithmica"},{"key":"9697_CR7","series-title":"Lect. Notes Comput. Sci.","doi-asserted-by":"crossref","first-page":"378","DOI":"10.1007\/978-3-642-02927-1_32","volume-title":"Proc. 36th ICALP, Part I","author":"M. Dom","year":"2009","unstructured":"Dom, M., Lokshtanov, D., Saurabh, S.: Incompressibility though colors and IDs. In: Proc. 36th ICALP, Part I. Lect. Notes Comput. Sci., vol. 5555, pp. 378\u2013389 (2009)"},{"key":"9697_CR8","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"R.G. Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, Berlin (1999)"},{"issue":"3","key":"9697_CR9","doi-asserted-by":"crossref","first-page":"698","DOI":"10.1016\/j.jcss.2011.10.001","volume":"78","author":"F.V. Fomin","year":"2012","unstructured":"Fomin, F.V., Lokshtanov, D., Raman, V., Saurabh, S., Rao, B.V.R.: Faster algorithms for finding and counting subgraphs. J. Comput. Syst. Sci. 78(3), 698\u2013706 (2012)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"9697_CR10","doi-asserted-by":"crossref","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. 289(1), 503\u2013516 (2002)","journal-title":"Theor. Comput. Sci."},{"key":"9697_CR11","volume-title":"Electronic Colloquium on Computational Complexity (ECCC)","author":"H. Fleischner","year":"2000","unstructured":"Fleischner, H., Szeider, S.: Polynomial-time recognition of minimal unsatisfiable formulas with fixed clause-variable difference. In: Electronic Colloquium on Computational Complexity (ECCC), vol. 7 (2000)"},{"key":"9697_CR12","volume-title":"Parameterized Complexity Theory","author":"J. Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Berlin (2006)"},{"issue":"41","key":"9697_CR13","doi-asserted-by":"crossref","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. 412(41), 5744\u20135751 (2011)","journal-title":"Theor. Comput. Sci."},{"key":"9697_CR14","series-title":"Lect. Notes Comput. Sci.","doi-asserted-by":"crossref","first-page":"138","DOI":"10.1007\/978-3-642-22953-4_12","volume-title":"Proc. FCT 2011","author":"G. Gutin","year":"2011","unstructured":"Gutin, G., Jones, M., Yeo, A.: A new bound for 3-satisfiable MaxSat and its algorithmic application. In: Proc. FCT 2011. Lect. Notes Comput. Sci., vol. 6914, pp. 138\u2013147 (2011)"},{"key":"9697_CR15","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1112\/plms\/s2-17.1.75","volume":"17","author":"G.H. Hardy","year":"1918","unstructured":"Hardy, G.H., Ramanujan, S.: Asymptotic formulae in combinatory analysis. Proc. Lond. Math. Soc. 17, 75\u2013115 (1918)","journal-title":"Proc. Lond. Math. Soc."},{"issue":"1\u20133","key":"9697_CR16","doi-asserted-by":"crossref","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 Appl. Math. 107(1\u20133), 83\u201398 (2000)","journal-title":"Discrete Appl. Math."},{"key":"9697_CR17","first-page":"339","volume-title":"Handbook of Satisfiability","author":"H. Kleine B\u00fcning","year":"2009","unstructured":"Kleine B\u00fcning, H., Kullmann, O.: Minimal unsatisfiability and autarkies. In: Handbook of Satisfiability, pp. 339\u2013401 (2009). Chap.\u00a011"},{"key":"9697_CR18","doi-asserted-by":"crossref","first-page":"116","DOI":"10.1109\/CCC.2000.856741","volume-title":"IEEE Conference on Computational Complexity","author":"O. Kullmann","year":"2000","unstructured":"Kullmann, O.: An application of matroid theory to the sat problem. In: IEEE Conference on Computational Complexity, pp. 116\u2013124 (2000)"},{"key":"9697_CR19","doi-asserted-by":"crossref","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. Discrete Appl. Math. 130, 209\u2013249 (2003)","journal-title":"Discrete Appl. Math."},{"key":"9697_CR20","doi-asserted-by":"crossref","DOI":"10.1090\/chel\/367","volume-title":"Matching Theory","author":"L. Lov\u00e1sz","year":"2009","unstructured":"Lov\u00e1sz, L., Plummer, M.D.: Matching Theory. AMS\/Chelsea, New York (2009)"},{"issue":"2","key":"9697_CR21","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1006\/jagm.1998.0996","volume":"31","author":"M. Mahajan","year":"1999","unstructured":"Mahajan, M., Raman, V.: Parameterizing above guaranteed values: MaxSat and MaxCut. J. Algorithms 31(2), 335\u2013354 (1999)","journal-title":"J. Algorithms"},{"issue":"2","key":"9697_CR22","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1016\/j.jcss.2008.08.004","volume":"75","author":"M. Mahajan","year":"2009","unstructured":"Mahajan, M., Raman, V., Sikdar, S.: Parameterizing above or below guaranteed values. J. Comput. Syst. Sci. 75(2), 137\u2013153 (2009). Preliminary version in the 2nd IWPEC, Lect. Notes Comput. Sci. 4169, 38\u201349 (2006)","journal-title":"J. Comput. Syst. Sci."},{"key":"9697_CR23","doi-asserted-by":"crossref","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 2 n steps. Discrete Appl. Math. 10, 287\u2013295 (1985)","journal-title":"Discrete Appl. Math."},{"key":"9697_CR24","doi-asserted-by":"crossref","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001","volume-title":"Invitation to Fixed-Parameter Algorithms","author":"R. Niedermeier","year":"2006","unstructured":"Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford University Press, Oxford (2006)"},{"key":"9697_CR25","volume-title":"Combinatorial Algorithms","author":"A. Nijenhuis","year":"1978","unstructured":"Nijenhuis, A., Wilf, H.S.: Combinatorial Algorithms. Academic Press, San Diego (1978)"},{"issue":"1","key":"9697_CR26","doi-asserted-by":"crossref","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. 37(1), 2\u201313 (1988)","journal-title":"J. Comput. Syst. Sci."},{"key":"9697_CR27","first-page":"268","volume-title":"STOC\u201995","author":"A. Srinivasan","year":"1995","unstructured":"Srinivasan, A.: Improved approximations of packing and covering problems. In: STOC\u201995, pp. 268\u2013276 (1995)"},{"issue":"4","key":"9697_CR28","doi-asserted-by":"crossref","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. 69(4), 656\u2013674 (2004)","journal-title":"J. Comput. Syst. Sci."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-012-9697-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-012-9697-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-012-9697-4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T09:45:10Z","timestamp":1559123110000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-012-9697-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,10,11]]},"references-count":28,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2014,3]]}},"alternative-id":["9697"],"URL":"https:\/\/doi.org\/10.1007\/s00453-012-9697-4","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,10,11]]}}}