{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T06:27:53Z","timestamp":1725863273357},"publisher-location":"Cham","reference-count":28,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319449524"},{"type":"electronic","value":"9783319449531"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-319-44953-1_16","type":"book-chapter","created":{"date-parts":[[2016,8,22]],"date-time":"2016-08-22T11:12:23Z","timestamp":1471864343000},"page":"233-250","source":"Crossref","is-referenced-by-count":0,"title":["Backdoors to Tractable Valued CSP"],"prefix":"10.1007","author":[{"given":"Robert","family":"Ganian","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"M. S.","family":"Ramanujan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stefan","family":"Szeider","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,8,23]]},"reference":[{"key":"16_CR1","unstructured":"Bessiere, C., Carbonnel, C., Hebrard, E., Katsirelos, G., Walsh, T.: Detecting and exploiting subproblem tractability. In: Rossi, F. (ed.) Proceedings of the 23rd International Joint Conference on Artificial Intelligence, IJCAI 2013, Beijing, China, 3\u20139 August. IJCAI\/AAAI (2013)"},{"issue":"2","key":"16_CR2","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1007\/s10601-015-9198-6","volume":"21","author":"C Carbonnel","year":"2016","unstructured":"Carbonnel, C., Cooper, M.C.: Tractability in constraint satisfaction problems: a survey. Constraints 21(2), 115\u2013144 (2016)","journal-title":"Constraints"},{"key":"16_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"224","DOI":"10.1007\/978-3-319-10428-7_18","volume-title":"Principles and Practice of Constraint Programming","author":"C Carbonnel","year":"2014","unstructured":"Carbonnel, C., Cooper, M.C., Hebrard, E.: On backdoors to tractable constraint languages. In: O\u2019Sullivan, B. (ed.) CP 2014. LNCS, vol. 8656, pp. 224\u2013239. Springer, Heidelberg (2014)"},{"issue":"1","key":"16_CR4","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1016\/j.tcs.2008.08.036","volume":"409","author":"DA Cohen","year":"2008","unstructured":"Cohen, D.A., Jeavons, P.G., Zivny, S.: The expressive power of valued constraints: hierarchies and collapses. Theoret. Comput. Sci. 409(1), 137\u2013153 (2008)","journal-title":"Theoret. Comput. Sci."},{"key":"16_CR5","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized Algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, New York (2015)"},{"key":"16_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"256","DOI":"10.1007\/978-3-540-74970-7_20","volume-title":"Principles and Practice of Constraint Programming \u2013 CP 2007","author":"BN Dilkina","year":"2007","unstructured":"Dilkina, B.N., Gomes, C.P., Sabharwal, A.: Tradeoffs in the complexity of backdoor detection. In: Bessi\u00e8re, C. (ed.) CP 2007. LNCS, vol. 4741, pp. 256\u2013270. Springer, Heidelberg (2007)"},{"key":"16_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1007\/978-3-642-02777-2_9","volume-title":"Theory and Applications of Satisfiability Testing - SAT 2009","author":"BN Dilkina","year":"2009","unstructured":"Dilkina, B.N., Gomes, C.P., Sabharwal, A.: Backdoors in the context of learning. In: Kullmann, O. (ed.) SAT 2009. LNCS, vol. 5584, pp. 73\u201379. Springer, Heidelberg (2009)"},{"key":"16_CR8","doi-asserted-by":"crossref","unstructured":"Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, New York (2013)","DOI":"10.1007\/978-1-4471-5559-1"},{"key":"16_CR9","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1016\/j.artint.2012.03.002","volume":"186","author":"W Dvor\u00e1k","year":"2012","unstructured":"Dvor\u00e1k, W., Ordyniak, S., Szeider, S.: Augmenting tractable fragments of abstract argumentation. Artif. Intell. 186, 157\u2013173 (2012)","journal-title":"Artif. Intell."},{"issue":"1","key":"16_CR10","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2818646","volume":"17","author":"JK Fichte","year":"2015","unstructured":"Fichte, J.K., Szeider, S.: Backdoors to normality for disjunctive logic programs. ACM Trans. Comput. Log. 17(1), 1\u201323 (2015)","journal-title":"ACM Trans. Comput. Log."},{"key":"16_CR11","doi-asserted-by":"crossref","first-page":"64","DOI":"10.1016\/j.artint.2014.12.001","volume":"220","author":"JK Fichte","year":"2015","unstructured":"Fichte, J.K., Szeider, S.: Backdoors to tractable answer set programming. Artif. Intell. 220, 64\u2013103 (2015)","journal-title":"Artif. Intell."},{"key":"16_CR12","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series, vol. XIV. Springer, Berlin (2006)"},{"key":"16_CR13","unstructured":"Ganian, R., Ordyniak, S.: The complexity landscape of decompositional parameters for ILP. In: Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence. AAAI Press (to appear, 2016)"},{"key":"16_CR14","doi-asserted-by":"crossref","unstructured":"Ganian, R., Ramanujan, M.S., Szeider, S.: Discovering archipelagos of tractability for constraint satisfaction and counting. In: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, 10\u201312 January, pp. 1670\u20131681 (2016)","DOI":"10.1137\/1.9781611974331.ch114"},{"key":"16_CR15","doi-asserted-by":"crossref","unstructured":"Gaspers, S., Misra, N., Ordyniak, S., Szeider, S., \u017divn\u00fd, S.: Backdoors into heterogeneous classes of SAT and CSP. In: Brodley, C.E., Stone, P. (eds.) Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence, Qu\u00e9bec City, Qu\u00e9bec, Canada, 27\u201331 July, pp. 2652\u20132658. AAAI Press (2014)","DOI":"10.1609\/aaai.v28i1.9111"},{"key":"16_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1007\/978-3-642-30891-8_15","volume-title":"The Multivariate Algorithmic Revolution and Beyond","author":"S Gaspers","year":"2012","unstructured":"Gaspers, S., Szeider, S.: Backdoors to satisfaction. In: Bodlaender, H.L., Downey, R., Fomin, F.V., Marx, D. (eds.) The Multivariate Algorithmic Revolution and Beyond. LNCS, vol. 7370, pp. 287\u2013317. Springer, Heidelberg (2012)"},{"key":"16_CR17","unstructured":"Jeavons, P., Krokhin, A.A., \u017divn\u00fd, S.: The complexity of valued constraint satisfaction. Bull. Eur. Assoc. Theoret. Comput. Sci. 113 (2014)"},{"key":"16_CR18","doi-asserted-by":"crossref","unstructured":"Kolmogorov, V., \u017divn\u00fd, S.: The complexity of conservative valued CSPs. J. ACM 60(2), Art. 10, 38 (2013)","DOI":"10.1145\/2450142.2450146"},{"key":"16_CR19","doi-asserted-by":"crossref","unstructured":"Krokhin, A., Bulatov, A., Jeavons, P.: The complexity of constraint satisfaction: an algebraic approach. In: Structural Theory of Automata, Semigroups and Universal Algebra, Montreal, 2003. NATO Science Series II: Mathematics, Physics, and Chemistry, vol. 207, pp. 181\u2013213 (2005)","DOI":"10.1007\/1-4020-3817-8_8"},{"key":"16_CR20","unstructured":"LeBras, R., Bernstein, R., Gomes, C.P., Selman, B., van Dover, R.B.: Crowdsourcing backdoor identification for combinatorial optimization. In Rossi, F. (ed.) Proceedings of the 23rd International Joint Conference on Artificial Intelligence, IJCAI 2013, Beijing, China, 3\u20139 August 2013"},{"key":"16_CR21","doi-asserted-by":"crossref","unstructured":"Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford Lecture Series in Mathematics and its Applications. Oxford University Press, Oxford (2006)","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001"},{"key":"16_CR22","unstructured":"Nishimura, N., Ragde, P., Szeider, S.: Detecting backdoor sets with respect to Horn and binary clauses. In: Proceedings of Seventh International Conference on Theory and Applications of Satisfiability Testing, SAT 2004, Vancouver, BC, Canada, 10\u201313 May, pp. 96\u2013103 (2004)"},{"issue":"3","key":"16_CR23","doi-asserted-by":"crossref","first-page":"407","DOI":"10.1006\/jcss.1999.1626","volume":"58","author":"CH Papadimitriou","year":"1999","unstructured":"Papadimitriou, C.H., Yannakakis, M.: On the complexity of database queries. J. Comput. Syst. Sci. 58(3), 407\u2013427 (1999)","journal-title":"J. Comput. Syst. Sci."},{"key":"16_CR24","doi-asserted-by":"crossref","unstructured":"Schaefer, T.J.: The complexity of satisfiability problems. In: Conference Record of the Tenth Annual ACM Symposium on Theory of Computing, San Diego, Calif., 1978, pp. 216\u2013226. ACM (1978)","DOI":"10.1145\/800133.804350"},{"issue":"4","key":"16_CR25","doi-asserted-by":"crossref","first-page":"2361","DOI":"10.1137\/140990346","volume":"29","author":"J Thapper","year":"2015","unstructured":"Thapper, J., \u017divn\u00fd, S.: Necessary conditions for tractability of valued CSPs. SIAM J. Discrete Math. 29(4), 2361\u20132384 (2015)","journal-title":"SIAM J. Discrete Math."},{"key":"16_CR26","doi-asserted-by":"crossref","unstructured":"\u017divn\u00fd, S.: The Complexity of Valued Constraint Satisfaction Problems. Cognitive Technologies. Springer, New York (2012)","DOI":"10.1007\/978-3-642-33974-5"},{"key":"16_CR27","unstructured":"Williams, R., Gomes, C., Selman, B.: Backdoors to typical case complexity. In: Gottlob, G., Walsh, T. (eds.) Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence, IJCAI 2003, pp. 1173\u20131178. Morgan Kaufmann (2003)"},{"key":"16_CR28","unstructured":"Williams, R., Gomes, C., Selman, B.: On the connections between backdoors, restarts, and heavy-tailedness in combinatorial search. In: Informal Proceedings of the Sixth International Conference on Theory and Applications of Satisfiability Testing, SAT 2003 S. Margherita Ligure - Portofino, Italy, 5\u20138 May, pp. 222\u2013230 (2003)"}],"container-title":["Lecture Notes in Computer Science","Principles and Practice of Constraint Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-44953-1_16","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,7,6]],"date-time":"2022-07-06T17:21:32Z","timestamp":1657128092000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-44953-1_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319449524","9783319449531"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-44953-1_16","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]}}}