{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T19:29:43Z","timestamp":1725564583052},"publisher-location":"Berlin, Heidelberg","reference-count":28,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540212362"},{"type":"electronic","value":"9783540247494"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-24749-4_14","type":"book-chapter","created":{"date-parts":[[2010,9,8]],"date-time":"2010-09-08T19:01:54Z","timestamp":1283972514000},"page":"152-163","source":"Crossref","is-referenced-by-count":1,"title":["Identifying Efficiently Solvable Cases of Max CSP"],"prefix":"10.1007","author":[{"given":"David","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":"14_CR1","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-58412-1","volume-title":"Complexity and Approximation","author":"G. Ausiello","year":"1999","unstructured":"Ausiello, G., Creszenzi, P., Gambosi, G., Kann, V., Marchetti-Spaccamela, A., Protasi, M.: Complexity and Approximation. Springer, Heidelberg (1999)"},{"key":"14_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"58","DOI":"10.1007\/978-3-540-45220-1_6","volume-title":"Computer Science Logic","author":"F. B\u00f6rner","year":"2003","unstructured":"B\u00f6rner, F., Bulatov, A., Jeavons, P., Krokhin, A.: Quantified constraints: Algorithms and complexity. In: Baaz, M., Makowsky, J.A. (eds.) CSL 2003. LNCS, vol.\u00a02803, pp. 58\u201370. Springer, Heidelberg (2003)"},{"key":"14_CR3","doi-asserted-by":"crossref","unstructured":"Bulatov, A.: A dichotomy theorem for constraints on a three-element set. In: Proceedings of FOCS 2002, pp. 649\u2013658 (2002)","DOI":"10.1109\/SFCS.2002.1181990"},{"key":"14_CR4","doi-asserted-by":"crossref","unstructured":"Bulatov, A.: Tractable conservative constraint satisfaction problems. In: Proceedings of LICS 2003, pp. 321\u2013330 (2003)","DOI":"10.1109\/LICS.2003.1210072"},{"key":"14_CR5","doi-asserted-by":"crossref","unstructured":"Bulatov, A., Dalmau, V.: Towards a dichotomy theorem for the counting constraint satisfaction problem. In: Proceedings of FOCS 2003, pp. 562\u2013571 (2003)","DOI":"10.1109\/SFCS.2003.1238229"},{"key":"14_CR6","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1016\/0166-218X(95)00103-X","volume":"70","author":"R.E. Burkard","year":"1996","unstructured":"Burkard, R.E., Klinz, B., Rudolf, R.: Perspectives of Monge properties in optimization. Discrete Applied Mathematics\u00a070, 95\u2013161 (1996)","journal-title":"Discrete Applied Mathematics"},{"key":"14_CR7","doi-asserted-by":"crossref","unstructured":"Creignou, N., Khanna, S., Sudan, M.: Complexity Classifications of Boolean Constraint Satisfaction Problems. SIAM Monographs on Discrete Mathematics and Applications, vol.\u00a07 (2001)","DOI":"10.1137\/1.9780898718546"},{"issue":"4","key":"14_CR8","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"},{"issue":"6","key":"14_CR9","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1016\/S0020-0190(02)00435-0","volume":"85","author":"M. Datar","year":"2003","unstructured":"Datar, M., Feder, T., Gionis, A., Motwani, R., Panigrahy, R.: A combinatorial algorithm for MAX CSP. Information Processing Letters\u00a085(6), 307\u2013315 (2003)","journal-title":"Information Processing Letters"},{"key":"14_CR10","volume-title":"Introduction to Lattices and Order","author":"B.A. Davey","year":"1990","unstructured":"Davey, B.A., Priestley, H.A.: Introduction to Lattices and Order. Cambridge University Press, Cambridge (1990)"},{"key":"14_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"224","DOI":"10.1007\/3-540-45726-7_18","volume-title":"Randomization and Approximation Techniques in Computer Science","author":"L. Engebretsen","year":"2002","unstructured":"Engebretsen, L., Guruswami, V.: Is constraint satisfaction over two variables always easy? In: Rolim, J.D.P., Vadhan, S.P. (eds.) RANDOM 2002. LNCS, vol.\u00a02483, pp. 224\u2013238. Springer, Heidelberg (2002)"},{"key":"14_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 on Computing\u00a028, 57\u2013104 (1998)","journal-title":"SIAM Journal on Computing"},{"key":"14_CR13","series-title":"Annals of Discrete Mathematics","volume-title":"Submodular Functions and Optimization","author":"S. Fujishige","year":"1991","unstructured":"Fujishige, S.: Submodular Functions and Optimization. Annals of Discrete Mathematics, vol.\u00a047. North-Holland, Amsterdam (1991)"},{"key":"14_CR14","doi-asserted-by":"publisher","first-page":"499","DOI":"10.1007\/BF01192523","volume":"15","author":"M.X. Goemans","year":"1995","unstructured":"Goemans, M.X., Ramakrishnan, V.S.: Minimizing submodular functions over families of subsets. Combinatorica\u00a015, 499\u2013513 (1995)","journal-title":"Combinatorica"},{"key":"14_CR15","doi-asserted-by":"publisher","first-page":"921","DOI":"10.1145\/48014.61051","volume":"35","author":"A. Goldberg","year":"1988","unstructured":"Goldberg, A., Tarjan, R.E.: A new approach to the maximum flow problem. Journal of the ACM\u00a035, 921\u2013940 (1988)","journal-title":"Journal of the ACM"},{"key":"14_CR16","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-97881-4","volume-title":"Geometric Algorithms and Combinatorial Optimization","author":"M. Gr\u00f6tschel","year":"1988","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization. Springer, New York (1988)"},{"key":"14_CR17","doi-asserted-by":"publisher","first-page":"798","DOI":"10.1145\/502090.502098","volume":"48","author":"J. H\u00e5stad","year":"2001","unstructured":"H\u00e5stad, J.: Some optimal inapproximability results. Journal of the ACM\u00a048, 798\u2013859 (2001)","journal-title":"Journal of the ACM"},{"issue":"4","key":"14_CR18","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"},{"key":"14_CR19","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, 185\u2013204 (1998)","journal-title":"Theoretical Computer Science"},{"issue":"1-2","key":"14_CR20","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/S0304-3975(98)00343-0","volume":"244","author":"P. Jonsson","year":"2000","unstructured":"Jonsson, P.: Boolean constraint satisfaction: Complexity results for optimization problems with arbitrary weights. Theoretical Computer Science\u00a0244(1-2), 189\u2013203 (2000)","journal-title":"Theoretical Computer Science"},{"key":"14_CR21","volume-title":"Submodular Functions and Electrical Networks","author":"H. Narayanan","year":"1997","unstructured":"Narayanan, H.: Submodular Functions and Electrical Networks. North-Holland, Amsterdam (1997)"},{"key":"14_CR22","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. Wiley, Chichester (1988)"},{"issue":"3","key":"14_CR23","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"C.H. Papadimitriou","year":"1991","unstructured":"Papadimitriou, C.H., Yannakakis, M.: Optimization, approximation, and complexity classes. Journal of Computer and System Sciences\u00a043(3), 425\u2013440 (1991)","journal-title":"Journal of Computer and System Sciences"},{"issue":"1","key":"14_CR24","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1016\/0166-218X(92)00189-S","volume":"52","author":"R. Rudolf","year":"1994","unstructured":"Rudolf, R.: Recognition of d-dimensional Monge arrays. Discrete Applied Mathematics\u00a052(1), 71\u201382 (1994)","journal-title":"Discrete Applied Mathematics"},{"key":"14_CR25","doi-asserted-by":"crossref","unstructured":"Schaefer, T.J.: The complexity of satisfiability problems. In: Proceedings STOC 1978, pp. 216\u2013226 (1978)","DOI":"10.1145\/800133.804350"},{"key":"14_CR26","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 polynomial time. Journal of Combinatorial Theory, Ser. B\u00a080, 346\u2013355 (2000)","journal-title":"Journal of Combinatorial Theory, Ser. B"},{"key":"14_CR27","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1016\/S0166-218X(97)00140-6","volume":"84","author":"A. Shioura","year":"1998","unstructured":"Shioura, A.: Minimization of an M-convex function. Discrete Applied Mathematics\u00a084, 215\u2013220 (1998)","journal-title":"Discrete Applied Mathematics"},{"key":"14_CR28","doi-asserted-by":"crossref","DOI":"10.1515\/9781400822539","volume-title":"Supermodularity and Complementarity","author":"D. Topkis","year":"1998","unstructured":"Topkis, D.: Supermodularity and Complementarity. Princeton University Press, Princeton (1998)"}],"container-title":["Lecture Notes in Computer Science","STACS 2004"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-24749-4_14","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,30]],"date-time":"2024-03-30T07:08:52Z","timestamp":1711782532000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-24749-4_14"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540212362","9783540247494"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-24749-4_14","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2004]]}}}