{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,7]],"date-time":"2024-09-07T16:59:09Z","timestamp":1725728349895},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642385353"},{"type":"electronic","value":"9783642385360"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-38536-0_28","type":"book-chapter","created":{"date-parts":[[2013,6,3]],"date-time":"2013-06-03T01:03:04Z","timestamp":1370221384000},"page":"322-333","source":"Crossref","is-referenced-by-count":4,"title":["QCSP on Partially Reflexive Cycles \u2013 The Wavy Line of Tractability"],"prefix":"10.1007","author":[{"given":"Florent","family":"Madelaine","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Barnaby","family":"Martin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"5","key":"28_CR1","doi-asserted-by":"publisher","first-page":"1782","DOI":"10.1137\/070708093","volume":"38","author":"L. Barto","year":"2009","unstructured":"Barto, L., Kozik, M., Niven, T.: The CSP dichotomy holds for digraphs with no sources and no sinks (a positive answer to a conjecture of Bang-Jensen and Hell). SIAM Journal on Computing\u00a038(5), 1782\u20131802 (2009)","journal-title":"SIAM Journal on Computing"},{"issue":"9","key":"28_CR2","doi-asserted-by":"publisher","first-page":"923","DOI":"10.1016\/j.ic.2009.05.003","volume":"207","author":"F. B\u00f6rner","year":"2009","unstructured":"B\u00f6rner, F., Bulatov, A.A., Chen, H., Jeavons, P., Krokhin, A.A.: The complexity of constraint satisfaction games and qcsp. Inf. Comput.\u00a0207(9), 923\u2013944 (2009)","journal-title":"Inf. Comput."},{"issue":"1","key":"28_CR3","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1145\/1120582.1120584","volume":"53","author":"A. Bulatov","year":"2006","unstructured":"Bulatov, A.: A dichotomy theorem for constraint satisfaction problems on a 3-element set. J. ACM\u00a053(1), 66\u2013120 (2006)","journal-title":"J. ACM"},{"key":"28_CR4","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.G.: Classifying the complexity of constraints using finite algebras. SIAM Journal on Computing\u00a034, 720\u2013742 (2005)","journal-title":"SIAM Journal on Computing"},{"issue":"5","key":"28_CR5","doi-asserted-by":"publisher","first-page":"1674","DOI":"10.1137\/060668572","volume":"37","author":"H. Chen","year":"2008","unstructured":"Chen, H.: The complexity of quantified constraint satisfaction: Collapsibility, sink algebras, and the three-element case. SIAM J. Comput.\u00a037(5), 1674\u20131701 (2008)","journal-title":"SIAM J. Comput."},{"key":"28_CR6","unstructured":"Chen, H. Meditations on quantified constraint satisfaction. CoRR abs\/1201.6306 (2012), Appeared in Festschrift for Dexter Kozen 60th."},{"key":"28_CR7","doi-asserted-by":"crossref","unstructured":"Chen, H., Madelaine, F., Martin, B.: Quantified constraints and containment problems. In: 23rd Annual IEEE Symposium on Logic in Computer Science, pp. 317\u2013328 (2008)","DOI":"10.1109\/LICS.2008.15"},{"issue":"4","key":"28_CR8","doi-asserted-by":"publisher","first-page":"821","DOI":"10.1016\/j.ejc.2007.11.020","volume":"29","author":"V. Dalmau","year":"2008","unstructured":"Dalmau, V., Krokhin, A.A.: Majority constraints have bounded pathwidth duality. Eur. J. Comb.\u00a029(4), 821\u2013837 (2008)","journal-title":"Eur. J. Comb."},{"issue":"2","key":"28_CR9","doi-asserted-by":"publisher","first-page":"236","DOI":"10.1006\/jctb.1997.1812","volume":"72","author":"T. Feder","year":"1998","unstructured":"Feder, T., Hell, P.: List homomorphisms to reflexive graphs. J. Comb. Theory, Ser. B\u00a072(2), 236\u2013250 (1998)","journal-title":"J. Comb. Theory, Ser. B"},{"issue":"1","key":"28_CR10","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1137\/080738866","volume":"24","author":"T. Feder","year":"2010","unstructured":"Feder, T., Hell, P., Jonsson, P., Krokhin, A.A., Nordh, G.: Retractions to pseudoforests. SIAM J. Discrete Math.\u00a024(1), 101\u2013112 (2010)","journal-title":"SIAM J. Discrete Math."},{"key":"28_CR11","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1137\/S0097539794266766","volume":"28","author":"T. Feder","year":"1999","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, 57\u2013104 (1999)","journal-title":"SIAM Journal on Computing"},{"key":"28_CR12","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1016\/0095-8956(90)90132-J","volume":"48","author":"P. Hell","year":"1990","unstructured":"Hell, P., Ne\u0161et\u0159il, J.: On the complexity of H-coloring. Journal of Combinatorial Theory, Series B\u00a048, 92\u2013110 (1990)","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"28_CR13","doi-asserted-by":"crossref","unstructured":"Madelaine, F., Martin, B.: A tetrachotomy for positive equality-free logic. In: Proceedings of the 26th Annual IEEE Symposium on Logic in Computer Science, LICS 2011 (2011)","DOI":"10.1109\/LICS.2011.27"},{"key":"28_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"480","DOI":"10.1007\/978-3-642-33558-7_36","volume-title":"Principles and Practice of Constraint Programming","author":"F. Madelaine","year":"2012","unstructured":"Madelaine, F., Martin, B.: Containment, equivalence and coreness from CSP to QCSP and beyond. In: Milano, M. (ed.) CP 2012. LNCS, vol.\u00a07514, pp. 480\u2013495. Springer, Heidelberg (2012)"},{"key":"28_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1007\/978-3-642-30642-6_24","volume-title":"Computer Science \u2013 Theory and Applications","author":"F. Madelaine","year":"2012","unstructured":"Madelaine, F., Martin, B., Stacho, J.: Constraint satisfaction with counting quantifiers. In: Hirsch, E.A., Karhum\u00e4ki, J., Lepist\u00f6, A., Prilutskii, M. (eds.) CSR 2012. LNCS, vol.\u00a07353, pp. 253\u2013265. Springer, Heidelberg (2012)"},{"key":"28_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"546","DOI":"10.1007\/978-3-642-23786-7_42","volume-title":"Principles and Practice of Constraint Programming \u2013 CP 2011","author":"B. Martin","year":"2011","unstructured":"Martin, B.: QCSP on partially reflexive forests. In: Lee, J. (ed.) CP 2011. LNCS, vol.\u00a06876, pp. 546\u2013560. Springer, Heidelberg (2011)"},{"key":"28_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"342","DOI":"10.1007\/11780342_36","volume-title":"Logical Approaches to Computational Barriers","author":"B. Martin","year":"2006","unstructured":"Martin, B., Madelaine, F.: Towards a trichotomy for quantified H-coloring. In: Beckmann, A., Berger, U., L\u00f6we, B., Tucker, J.V. (eds.) CiE 2006. LNCS, vol.\u00a03988, pp. 342\u2013352. Springer, Heidelberg (2006)"},{"key":"28_CR18","unstructured":"Papadimitriou, C.H.: Computational Complexity. Addison-Wesley (1994)"},{"issue":"4","key":"28_CR19","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1391289.1391291","volume":"55","author":"O. Reingold","year":"2008","unstructured":"Reingold, O.: Undirected connectivity in log-space. J. ACM\u00a055(4), 1\u201324 (2008)","journal-title":"J. ACM"},{"key":"28_CR20","doi-asserted-by":"crossref","unstructured":"Schaefer, T.J.: The complexity of satisfiability problems. In: Proceedings of STOC 1978, pp. 216\u2013226 (1978)","DOI":"10.1145\/800133.804350"}],"container-title":["Lecture Notes in Computer Science","Computer Science \u2013 Theory and Applications"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-38536-0_28","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,13]],"date-time":"2019-05-13T16:58:46Z","timestamp":1557766726000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-38536-0_28"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642385353","9783642385360"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-38536-0_28","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}