{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T19:01:38Z","timestamp":1725562898454},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642151545"},{"type":"electronic","value":"9783642151552"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-15155-2_43","type":"book-chapter","created":{"date-parts":[[2010,8,13]],"date-time":"2010-08-13T20:17:45Z","timestamp":1281730665000},"page":"489-500","source":"Crossref","is-referenced-by-count":8,"title":["Parameterized Complexity and Kernelizability of Max Ones and Exact Ones Problems"],"prefix":"10.1007","author":[{"given":"Stefan","family":"Kratsch","sequence":"first","affiliation":[]},{"given":"D\u00e1niel","family":"Marx","sequence":"additional","affiliation":[]},{"given":"Magnus","family":"Wahlstr\u00f6m","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"43_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"563","DOI":"10.1007\/978-3-540-70575-8_46","volume-title":"Automata, Languages and Programming","author":"H.L. Bodlaender","year":"2008","unstructured":"Bodlaender, H.L., Downey, R.G., Fellows, M.R., Hermelin, D.: On problems without polynomial kernels (extended abstract). In: Aceto, L., Damg\u00e5rd, I., Goldberg, L.A., Halld\u00f3rsson, M.M., Ing\u00f3lfsd\u00f3ttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part I. LNCS, vol.\u00a05125, pp. 563\u2013574. Springer, Heidelberg (2008)"},{"key":"43_CR2","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":"43_CR3","first-page":"649","volume-title":"Proc. 43th Symp. Foundations of Computer Science","author":"A.A. Bulatov","year":"2002","unstructured":"Bulatov, A.A.: A dichotomy theorem for constraints on a three-element set. In: Proc. 43th Symp. Foundations of Computer Science, pp. 649\u2013658. IEEE, Los Alamitos (2002)"},{"key":"43_CR4","first-page":"321","volume-title":"LICS","author":"A.A. Bulatov","year":"2003","unstructured":"Bulatov, A.A.: Tractable conservative constraint satisfaction problems. In: LICS, p. 321. IEEE, Los Alamitos (2003)"},{"key":"43_CR5","doi-asserted-by":"crossref","unstructured":"Creignou, N., Khanna, S., Sudan, M.: Complexity Classifications of Boolean Constraint Satisfaction Problems. In: SIAM Monographs on Discrete Mathematics and Applications, vol.\u00a07 (2001)","DOI":"10.1137\/1.9780898718546"},{"key":"43_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1007\/978-3-540-87531-4_10","volume-title":"Computer Science Logic","author":"N. Creignou","year":"2008","unstructured":"Creignou, N., Schnoor, H., Schnoor, I.: Non-uniform boolean constraint satisfaction problems with cardinality constraint. In: Kaminski, M., Martini, S. (eds.) CSL 2008. LNCS, vol.\u00a05213, pp. 109\u2013123. Springer, Heidelberg (2008)"},{"issue":"1","key":"43_CR7","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/S0304-3975(01)00146-3","volume":"288","author":"P. Crescenzi","year":"2002","unstructured":"Crescenzi, P., Rossi, G.: On the Hamming distance of constraint satisfaction problems. Theoretical Computer Science\u00a0288(1), 85\u2013100 (2002)","journal-title":"Theoretical Computer Science"},{"key":"43_CR8","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. LNCS, vol.\u00a05555, pp. 378\u2013389. Springer, Heidelberg (2009)"},{"key":"43_CR9","volume-title":"Monographs in Computer Science","author":"R.G. Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. In: Monographs in Computer Science. Springer, New York (1999)"},{"issue":"1","key":"43_CR10","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1137\/S0097539794266766","volume":"28","author":"T. Feder","year":"1999","unstructured":"Feder, T., Vardi, M.Y.: The computational structure of monotone monadic SNP and constraint satisfaction: a study through Datalog and group theory. SIAM J. Comput.\u00a028(1), 57\u2013104 (1999)","journal-title":"SIAM J. Comput."},{"key":"43_CR11","volume-title":"Parameterized Complexity Theory","author":"J. Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Heidelberg (2006)"},{"issue":"6","key":"43_CR12","doi-asserted-by":"publisher","first-page":"1863","DOI":"10.1137\/S0097539799349948","volume":"30","author":"S. Khanna","year":"2000","unstructured":"Khanna, S., Sudan, M., Trevisan, L., Williamson, D.P.: The approximability of constraint satisfaction problems. SIAM J. Comput.\u00a030(6), 1863\u20131920 (2000)","journal-title":"SIAM J. Comput."},{"key":"43_CR13","doi-asserted-by":"crossref","unstructured":"Kratsch, S., Wahlstr\u00f6m, M.: Preprocessing of min ones problems: A dichotomy. In: ICALP (2010) (to appear)","DOI":"10.1007\/978-3-642-14165-2_55"},{"key":"43_CR14","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1145\/321864.321877","volume":"22","author":"R.E. Ladner","year":"1975","unstructured":"Ladner, R.E.: On the structure of polynomial time reducibility. J. Assoc. Comput. Mach.\u00a022, 155\u2013171 (1975)","journal-title":"J. Assoc. Comput. Mach."},{"issue":"2","key":"43_CR15","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1007\/s00037-005-0195-9","volume":"14","author":"D. Marx","year":"2005","unstructured":"Marx, D.: Parameterized complexity of constraint satisfaction problems. Computational Complexity\u00a014(2), 153\u2013183 (2005)","journal-title":"Computational Complexity"},{"key":"43_CR16","doi-asserted-by":"publisher","first-page":"232","DOI":"10.1007\/BF01580444","volume":"8","author":"G.L. Nemhauser","year":"1975","unstructured":"Nemhauser, G.L., Trotter Jr., L.E.: Vertex packings: structural properties and algorithms. Math. Programming\u00a08, 232\u2013248 (1975)","journal-title":"Math. Programming"},{"key":"43_CR17","doi-asserted-by":"crossref","unstructured":"Nordh, G., Zanuttini, B.: Frozen boolean partial co-clones. In: ISMVL, pp. 120\u2013125 (2009)","DOI":"10.1109\/ISMVL.2009.10"},{"key":"43_CR18","first-page":"216","volume-title":"STOC","author":"T.J. Schaefer","year":"1978","unstructured":"Schaefer, T.J.: The complexity of satisfiability problems. In: STOC, pp. 216\u2013226. ACM, New York (1978)"},{"issue":"6","key":"43_CR19","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1016\/j.ipl.2008.11.004","volume":"109","author":"R. Williams","year":"2009","unstructured":"Williams, R.: Finding paths of length k in O *(2 k ) time. Inf. Process. Lett.\u00a0109(6), 315\u2013318 (2009)","journal-title":"Inf. Process. Lett."}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2010"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-15155-2_43.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,24]],"date-time":"2020-11-24T03:01:44Z","timestamp":1606186904000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-15155-2_43"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642151545","9783642151552"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-15155-2_43","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}