{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T06:16:42Z","timestamp":1725603402788},"publisher-location":"Berlin, Heidelberg","reference-count":29,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642237850"},{"type":"electronic","value":"9783642237867"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"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":[[2011]]},"DOI":"10.1007\/978-3-642-23786-7_17","type":"book-chapter","created":{"date-parts":[[2011,8,31]],"date-time":"2011-08-31T03:58:42Z","timestamp":1314763122000},"page":"195-209","source":"Crossref","is-referenced-by-count":1,"title":["Tractable Triangles"],"prefix":"10.1007","author":[{"given":"Martin C.","family":"Cooper","sequence":"first","affiliation":[]},{"given":"Stanislav","family":"\u017divn\u00fd","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"17_CR1","volume-title":"Nonserial dynamic programming","author":"U. Bertel\u00e9","year":"1972","unstructured":"Bertel\u00e9, U., Brioshi, F.: Nonserial dynamic programming. Academic Press, London (1972)"},{"issue":"2","key":"17_CR2","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1145\/256303.256306","volume":"44","author":"S. Bistarelli","year":"1997","unstructured":"Bistarelli, S., Montanari, U., Rossi, F.: Semiring-based Constraint Satisfaction and Optimisation. Journal of the ACM\u00a044(2), 201\u2013236 (1997)","journal-title":"Journal of the ACM"},{"issue":"3","key":"17_CR3","doi-asserted-by":"publisher","first-page":"720","DOI":"10.1137\/S0097539700376676","volume":"34","author":"A. Bulatov","year":"2005","unstructured":"Bulatov, A., Krokhin, A., Jeavons, P.: Classifying the Complexity of Constraints using Finite Algebras. SIAM Journal on Computing\u00a034(3), 720\u2013742 (2005)","journal-title":"SIAM Journal on Computing"},{"issue":"1-3","key":"17_CR4","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1016\/j.tcs.2008.03.015","volume":"401","author":"D.A. Cohen","year":"2008","unstructured":"Cohen, D.A., Cooper, M.C., Jeavons, P.G.: Generalising submodularity and Horn clauses: Tractable optimization problems defined by tournament pair multimorphisms. Theoretical Computer Science\u00a0401(1-3), 36\u201351 (2008)","journal-title":"Theoretical Computer Science"},{"issue":"11","key":"17_CR5","doi-asserted-by":"publisher","first-page":"983","DOI":"10.1016\/j.artint.2006.04.002","volume":"170","author":"D.A. Cohen","year":"2006","unstructured":"Cohen, D.A., Cooper, M.C., Jeavons, P.G., Krokhin, A.A.: The Complexity of Soft Constraint Satisfaction. Artificial Intelligence\u00a0170(11), 983\u20131016 (2006)","journal-title":"Artificial Intelligence"},{"key":"17_CR6","volume-title":"The Handbook of Constraint Programming","author":"D. Cohen","year":"2006","unstructured":"Cohen, D., Jeavons, P.: The complexity of constraint languages. In: Rossi, F., van Beek, P., Walsh, T. (eds.) The Handbook of Constraint Programming. Elsevier, Amsterdam (2006)"},{"key":"17_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"807","DOI":"10.1007\/978-3-540-45193-8_57","volume-title":"Principles and Practice of Constraint Programming \u2013 CP 2003","author":"D.A. Cohen","year":"2003","unstructured":"Cohen, D.A.: A New Class of Binary CSPs for which Arc-Constistency Is a Decision Procedure. In: Rossi, F. (ed.) CP 2003. LNCS, vol.\u00a02833, pp. 807\u2013811. Springer, Heidelberg (2003)"},{"issue":"9-10","key":"17_CR8","doi-asserted-by":"publisher","first-page":"570","DOI":"10.1016\/j.artint.2010.03.002","volume":"174","author":"M.C. Cooper","year":"2010","unstructured":"Cooper, M.C., Jeavons, P.G., Salamon, A.Z.: Generalizing constraint satisfaction on trees: hybrid tractability and variable elimination. Artificial Intelligence\u00a0174(9-10), 570\u2013584 (2010)","journal-title":"Artificial Intelligence"},{"issue":"9-10","key":"17_CR9","doi-asserted-by":"publisher","first-page":"1555","DOI":"10.1016\/j.artint.2011.02.003","volume":"175","author":"M.C. Cooper","year":"2011","unstructured":"Cooper, M.C., \u017divn\u00fd, S.: Hybrid tractability of valued constraint problems. Artificial Intelligence\u00a0175(9-10), 1555\u20131569 (2011)","journal-title":"Artificial Intelligence"},{"key":"17_CR10","series-title":"LNCS","first-page":"187","volume-title":"CP 2011","author":"M.C. Cooper","year":"2011","unstructured":"Cooper, M.C., \u017divn\u00fd, S.: Hierarchically nested convex VCSP. In: Lee, J. (ed.) CP 2011. LNCS, vol.\u00a06876, pp. 187\u2013194. Springer, Heidelberg (2011)"},{"key":"17_CR11","series-title":"SIAM Monographs on Discrete Mathematics and Applications","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898718546","volume-title":"Complexity Classification of Boolean Constraint Satisfaction Problems","author":"N. Creignou","year":"2001","unstructured":"Creignou, N., Khanna, S., Sudan, M.: Complexity Classification of Boolean Constraint Satisfaction Problems. SIAM Monographs on Discrete Mathematics and Applications, vol.\u00a07. SIAM, Philadelphia (2001)"},{"key":"17_CR12","volume-title":"Constraint Processing","author":"R. Dechter","year":"2003","unstructured":"Dechter, R.: Constraint Processing. Morgan Kaufmann, San Francisco (2003)"},{"issue":"1","key":"17_CR13","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0004-3702(87)90002-6","volume":"34","author":"R. Dechter","year":"1988","unstructured":"Dechter, R., Pearl, J.: Network-based Heuristics for Constraint Satisfaction Problems. Artificial Intelligence\u00a034(1), 1\u201338 (1988)","journal-title":"Artificial Intelligence"},{"key":"17_CR14","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parametrized Complexity","author":"R. Downey","year":"1999","unstructured":"Downey, R., Fellows, M.: Parametrized Complexity. Springer, Heidelberg (1999)"},{"key":"17_CR15","doi-asserted-by":"publisher","first-page":"449","DOI":"10.4153\/CJM-1965-045-4","volume":"17","author":"J. Edmonds","year":"1965","unstructured":"Edmonds, J.: Paths, trees, and flowers. Canadian Journal of Mathematics\u00a017, 449\u2013467 (1965)","journal-title":"Canadian Journal of Mathematics"},{"issue":"1","key":"17_CR16","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1137\/S0097539794266766","volume":"28","author":"T. Feder","year":"1998","unstructured":"Feder, T., Vardi, M.: The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory. SIAM Journal on Computing\u00a028(1), 57\u2013104 (1998)","journal-title":"SIAM Journal on Computing"},{"key":"17_CR17","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M. Garey","year":"1979","unstructured":"Garey, M., Johnson, D.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman, New York (1979)"},{"issue":"9","key":"17_CR18","doi-asserted-by":"publisher","first-page":"778","DOI":"10.2307\/2310464","volume":"66","author":"A.W. Goodman","year":"1959","unstructured":"Goodman, A.W.: On Sets of Acquaintances and Strangers at any Party. The American Mathematical Monthly\u00a066(9), 778\u2013783 (1959)","journal-title":"The American Mathematical Monthly"},{"issue":"1","key":"17_CR19","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1206035.1206036","volume":"54","author":"M. Grohe","year":"2007","unstructured":"Grohe, M.: The complexity of homomorphism and constraint satisfaction problems seen from the other side. Journal of the ACM\u00a054(1), 1\u201324 (2007)","journal-title":"Journal of the ACM"},{"issue":"1-2","key":"17_CR20","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1016\/S0304-3975(97)00230-2","volume":"200","author":"P. Jeavons","year":"1998","unstructured":"Jeavons, P.: On the Algebraic Structure of Combinatorial Problems. Theoretical Computer Science\u00a0200(1-2), 185\u2013204 (1998)","journal-title":"Theoretical Computer Science"},{"key":"17_CR21","unstructured":"Kolmogorov, V., \u017divn\u00fd, S.: Generalising tractable VCSPs defined by symmetric tournament pair multimorphisms. Tech. rep. (August 2010)"},{"key":"17_CR22","doi-asserted-by":"crossref","unstructured":"Kolmogorov, V., \u017divn\u00fd, S.: The complexity of conservative VCSPs (submitted for publication, 2011)","DOI":"10.1137\/1.9781611973099.61"},{"issue":"2","key":"17_CR23","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1016\/0022-0000(80)90060-4","volume":"20","author":"J.M. Lewis","year":"1980","unstructured":"Lewis, J.M., Yannakakis, M.: The node-deletion problem for hereditary properties is NP-complete. Journal of Computer System Sciences\u00a020(2), 219\u2013230 (1980)","journal-title":"Journal of Computer System Sciences"},{"key":"17_CR24","unstructured":"Lov\u00e1sz, L.: Coverings and colorings of hypergraphs. In: Proceedings of the 4th Southeastern Conference on Combinatorics, Graph Theory and Computing, pp. 3\u201312 (1973)"},{"issue":"1-3","key":"17_CR25","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1016\/S0012-365X(97)89267-9","volume":"162","author":"F. Maffray","year":"1996","unstructured":"Maffray, F., Preissmann, M.: On the NP-completeness of the k-colorability problem for triangle-free graphs. Discrete Mathematics\u00a0162(1-3), 313\u2013317 (1996)","journal-title":"Discrete Mathematics"},{"key":"17_CR26","volume-title":"Computational Complexity","author":"C. Papadimitriou","year":"1994","unstructured":"Papadimitriou, C.: Computational Complexity. Addison-Wesley, Reading (1994)"},{"volume-title":"The Handbook of Constraint Programming","year":"2006","key":"17_CR27","unstructured":"Rossi, F., van Beek, P., Walsh, T. (eds.): The Handbook of Constraint Programming. Elsevier, Amsterdam (2006)"},{"key":"17_CR28","doi-asserted-by":"crossref","unstructured":"Schaefer, T.: The Complexity of Satisfiability Problems. In: Proceedings of the 10th Annual ACM Symposium on Theory of Computing (STOC 1978), pp. 216\u2013226 (1978)","DOI":"10.1145\/800133.804350"},{"key":"17_CR29","unstructured":"Schiex, T., Fargier, H., Verfaillie, G.: Valued Constraint Satisfaction Problems: Hard and Easy Problems. In: Proceedings of the 14th International Joint Conference on Artificial Intelligence, IJCAI 1995 (1995)"}],"container-title":["Lecture Notes in Computer Science","Principles and Practice of Constraint Programming \u2013 CP 2011"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-23786-7_17","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,14]],"date-time":"2019-06-14T12:36:36Z","timestamp":1560515796000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-23786-7_17"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642237850","9783642237867"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-23786-7_17","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}