{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T19:35:37Z","timestamp":1725564937069},"publisher-location":"Berlin, Heidelberg","reference-count":31,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540202028"},{"type":"electronic","value":"9783540451938"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/978-3-540-45193-8_17","type":"book-chapter","created":{"date-parts":[[2010,9,8]],"date-time":"2010-09-08T23:35:03Z","timestamp":1283988903000},"page":"244-258","source":"Crossref","is-referenced-by-count":9,"title":["Soft Constraints: Complexity and Multimorphisms"],"prefix":"10.1007","author":[{"given":"David A.","family":"Cohen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Martin","family":"Cooper","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Peter","family":"Jeavons","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andrei","family":"Krokhin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"17_CR1","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1023\/A:1026441215081","volume":"4","author":"S. Bistarelli","year":"1999","unstructured":"Bistarelli, S., Fargier, H., Montanari, U., Rossi, F., Schiex, T., Verfaillie, G.: Semiring-based CSPs and valued CSPs: Frameworks, properties, and comparison. Constraints\u00a04, 199\u2013240 (1999)","journal-title":"Constraints"},{"key":"17_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"118","DOI":"10.1007\/978-3-540-48085-3_9","volume-title":"Principles and Practice of Constraint Programming \u2013 CP\u201999","author":"M. Bj\u00e4reland","year":"1999","unstructured":"Bj\u00e4reland, M., Jonsson, P.: Exploiting bipartiteness to identify yet another tractable subclass of CSP. In: Jaffar, J. (ed.) CP 1999. LNCS, vol.\u00a01713, pp. 118\u2013128. Springer, Heidelberg (1999)"},{"key":"17_CR3","doi-asserted-by":"publisher","first-page":"649","DOI":"10.1109\/SFCS.2002.1181990","volume-title":"Proceedings 43rd IEEE Symposium on Foundations of Computer Science, FOCS 2002","author":"A.A. Bulatov","year":"2002","unstructured":"Bulatov, A.A.: A dichotomy theorem for constraints on a three-element set. In: Proceedings 43rd IEEE Symposium on Foundations of Computer Science, FOCS 2002, pp. 649\u2013658. IEEE Computer Society, Los Alamitos (2002)"},{"key":"17_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"272","DOI":"10.1007\/3-540-45022-X_24","volume-title":"Automata, Languages and Programming","author":"A.A. Bulatov","year":"2000","unstructured":"Bulatov, A.A., Krokhin, A.A., Jeavons, P.G.: Constraint satisfaction problems and finite algebras. In: Welzl, E., Montanari, U., Rolim, J.D.P. (eds.) ICALP 2000. LNCS, vol.\u00a01853, pp. 272\u2013282. Springer, Heidelberg (2000)"},{"key":"17_CR5","doi-asserted-by":"crossref","unstructured":"Bulatov, A.A., Krokhin, A.A., Jeavons, P.G.: The complexity of maximal constraint languages. In: Proceedings 33rd ACM Symposium on Theory of Computing, STOC 2001, pp. 667\u2013674 (2001)","DOI":"10.1145\/380752.380868"},{"key":"17_CR6","unstructured":"Cohen, D., Cooper, M., Jeavons, P., Krokhin, A.: A tractable class of soft constraints. Technical Report CSD-TR-02-14, Computer Science Department, Royal Holloway, University of London, Egham, Surrey, UK (short version to appear in Proceedings of IJCAI 2003) (December 2002)"},{"key":"17_CR7","unstructured":"Cohen, D., Cooper, M., Jeavons, P., Krokhin, A.: An investigation of the multimorphisms of tractable and intractable classes of valued constraints. Technical Report CSD-TR-03-03, Computer Science Department, Royal Holloway, University of London, Egham, Surrey, UK (2003)"},{"key":"17_CR8","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1016\/0004-3702(94)90021-3","volume":"65","author":"M.C. Cooper","year":"1994","unstructured":"Cooper, M.C., Cohen, D.A., Jeavons, P.G.: Characterising tractable constraints. Artificial Intelligence\u00a065, 347\u2013361 (1994)","journal-title":"Artificial Intelligence"},{"key":"17_CR9","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, Society for Industrial and Applied Mathematics, Philadelphia, PA, vol.\u00a07 (2001)"},{"issue":"2","key":"17_CR10","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1002\/net.3230150206","volume":"15","author":"W.H. Cunningham","year":"1985","unstructured":"Cunningham, W.H.: Minimum cuts, modular functions, and matroid polyhedra. Networks\u00a015(2), 205\u2013215 (1985)","journal-title":"Networks"},{"issue":"4","key":"17_CR11","doi-asserted-by":"publisher","first-page":"864","DOI":"10.1137\/S0097539792225297","volume":"23","author":"E. Dahlhaus","year":"1994","unstructured":"Dahlhaus, E., Johnson, D.S., Papadimitriou, C.H., Seymour, P.D., Yannakakis, M.: The complexity of multiterminal cuts. SIAM Journal on Computing\u00a023(4), 864\u2013894 (1994)","journal-title":"SIAM Journal on Computing"},{"key":"17_CR12","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1137\/S0097539794266766","volume":"28","author":"T. Feder","year":"1998","unstructured":"Feder, T., Vardi, M.Y.: The computational structure of monotone monadic SNP and constraint satisfaction: A study through Datalog and group theory. SIAM Journal of Computing\u00a028, 57\u2013104 (1998)","journal-title":"SIAM Journal of Computing"},{"key":"17_CR13","doi-asserted-by":"crossref","unstructured":"Fleischer, L., Iwata, S.: Improved algorithms for submodular function minimization and submodular flow. In: Proceedings of the 32th Annual ACM Symposium on Theory of Computing, pp. 107\u2013116 (2000)","DOI":"10.1145\/335305.335318"},{"key":"17_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"160","DOI":"10.1007\/3-540-45535-3_13","volume-title":"Integer Programming and Combinatorial Optimization","author":"S. Fujishige","year":"2001","unstructured":"Fujishige, S., Iwata, S.: Bisubmodular function minimization. In: Aardal, K., Gerards, B. (eds.) IPCO 2001. LNCS, vol.\u00a02081, p. 160. Springer, Heidelberg (2001)"},{"key":"17_CR15","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M. Garey","year":"1979","unstructured":"Garey, M., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, San Francisco (1979)"},{"key":"17_CR16","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1007\/BF02579273","volume":"1","author":"M. Gr\u00f6tschel","year":"1981","unstructured":"Gr\u00f6tschel, M., Lovasz, L., Schrijver, A.: The ellipsoid method and its consequences in combinatorial optimization. Combinatorica\u00a01, 169\u2013198 (1981)","journal-title":"Combinatorica"},{"issue":"4","key":"17_CR17","doi-asserted-by":"publisher","first-page":"761","DOI":"10.1145\/502090.502096","volume":"48","author":"S. Iwata","year":"2001","unstructured":"Iwata, S., Fleischer, L., Fujishige, S.: A combinatorial strongly polynomial algorithm for minimizing submodular functions. Journal of the ACM\u00a048(4), 761\u2013777 (2001)","journal-title":"Journal of the ACM"},{"issue":"1\u20132","key":"17_CR18","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1016\/S0004-3702(98)00022-8","volume":"101","author":"P.G. Jeavons","year":"1998","unstructured":"Jeavons, P.G., Cohen, D.A., Cooper, M.C.: Constraints, consistency and closure. Artificial Intelligence\u00a0101(1\u20132), 251\u2013265 (1998)","journal-title":"Artificial Intelligence"},{"key":"17_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1007\/3-540-61551-2_80","volume-title":"Principles and Practice of Constraint Programming - CP\u201996","author":"P.G. Jeavons","year":"1996","unstructured":"Jeavons, P.G., Cohen, D.A., Gyssens, M.: A test for tractability. In: Freuder, E.C. (ed.) CP 1996. LNCS, vol.\u00a01118, pp. 267\u2013281. Springer, Heidelberg (1996)"},{"key":"17_CR20","doi-asserted-by":"publisher","first-page":"527","DOI":"10.1145\/263867.263489","volume":"44","author":"P.G. Jeavons","year":"1997","unstructured":"Jeavons, P.G., Cohen, D.A., Gyssens, M.: Closure properties of constraints. Journal of the ACM\u00a044, 527\u2013548 (1997)","journal-title":"Journal of the ACM"},{"key":"17_CR21","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1023\/A:1009890709297","volume":"4","author":"P.G. Jeavons","year":"1999","unstructured":"Jeavons, P.G., Cohen, D.A., Gyssens, M.: How to determine the expressive power of constraints. Constraints\u00a04, 113\u2013131 (1999)","journal-title":"Constraints"},{"key":"17_CR22","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1023\/A:1018941030227","volume":"24","author":"P.G. Jeavons","year":"1998","unstructured":"Jeavons, P.G., Cohen, D.A., Pearson, J.K.: Constraints and universal algebra. Annals of Mathematics and Artificial Intelligence\u00a024, 51\u201367 (1998)","journal-title":"Annals of Mathematics and Artificial Intelligence"},{"issue":"2","key":"17_CR23","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1016\/0004-3702(95)00107-7","volume":"79","author":"P.G. Jeavons","year":"1995","unstructured":"Jeavons, P.G., Cooper, M.C.: Tractable constraints on ordered domains. Artificial Intelligence\u00a079(2), 327\u2013339 (1995)","journal-title":"Artificial Intelligence"},{"key":"17_CR24","unstructured":"Khatib, L., Morris, P., Morris, R., Rossi, F.: Temporal constraint reasoning with preferences. In: Proceedings of the 17th International Joint Conference on Artificial Intelligence (IJCAI 2001), Seattle, USA, pp. 322\u2013327 (2001)"},{"key":"17_CR25","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1016\/0004-3702(93)90063-H","volume":"64","author":"L. Kirousis","year":"1993","unstructured":"Kirousis, L.: Fast parallel constraint satisfaction. Artificial Intelligence\u00a064, 147\u2013160 (1993)","journal-title":"Artificial Intelligence"},{"key":"17_CR26","doi-asserted-by":"crossref","DOI":"10.1002\/9781118627372","volume-title":"Integer and Combinatorial Optimization","author":"G.L. Nemhauser","year":"1988","unstructured":"Nemhauser, G.L., Wolsey, L.A.: Integer and Combinatorial Optimization. John Wiley & Sons, Chichester (1988)"},{"key":"17_CR27","unstructured":"Pearson, J.K., Jeavons, P.G.: A survey of tractable constraint satisfaction problems. Technical Report CSD-TR-97-15, Royal Holloway, Univ. of London (1997)"},{"key":"17_CR28","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-0348-5547-1","volume-title":"Funktionen- und Relationenalgebren","author":"R. P\u00f6schel","year":"1979","unstructured":"P\u00f6schel, R., Kalu\u017enin, L.A.: Funktionen- und Relationenalgebren. DVW, Berlin (1979)"},{"key":"17_CR29","doi-asserted-by":"crossref","unstructured":"Schaefer, T.J.: The complexity of satisfiability problems. In: Proceedings 10th ACM Symposium on Theory of Computing, STOC 1978, pp. 216\u2013226 (1978)","DOI":"10.1145\/800133.804350"},{"key":"17_CR30","doi-asserted-by":"publisher","first-page":"346","DOI":"10.1006\/jctb.2000.1989","volume":"80","author":"A. Schrijver","year":"2000","unstructured":"Schrijver, A.: A combinatorial algorithm minimizing submodular functions in strongly polynomial time. JCTB: Journal of Combinatorial Theory, Series B\u00a080, 346\u2013355 (2000)","journal-title":"JCTB: Journal of Combinatorial Theory, Series B"},{"key":"17_CR31","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1016\/0004-3702(92)90020-X","volume":"57","author":"P. Hentenryck van","year":"1992","unstructured":"van Hentenryck, P., Deville, Y., Teng, C.-M.: A generic arc-consistency algorithm and its specializations. Artificial Intelligence\u00a057, 291\u2013321 (1992)","journal-title":"Artificial Intelligence"}],"container-title":["Lecture Notes in Computer Science","Principles and Practice of Constraint Programming \u2013 CP 2003"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-45193-8_17","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,30]],"date-time":"2024-03-30T07:27:31Z","timestamp":1711783651000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-45193-8_17"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540202028","9783540451938"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-45193-8_17","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2003]]}}}