{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,8]],"date-time":"2024-09-08T11:45:06Z","timestamp":1725795906780},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662439470"},{"type":"electronic","value":"9783662439487"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-662-43948-7_70","type":"book-chapter","created":{"date-parts":[[2014,6,11]],"date-time":"2014-06-11T12:10:36Z","timestamp":1402488636000},"page":"847-858","source":"Crossref","is-referenced-by-count":0,"title":["QCSP on Semicomplete Digraphs"],"prefix":"10.1007","author":[{"given":"Petar","family":"Dapi\u0107","sequence":"first","affiliation":[]},{"given":"Petar","family":"Markovi\u0107","sequence":"additional","affiliation":[]},{"given":"Barnaby","family":"Martin","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"3","key":"70_CR1","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1137\/0401029","volume":"1","author":"J. Bang-Jensen","year":"1988","unstructured":"Bang-Jensen, J., Hell, P., MacGillivray, G.: The complexity of colouring by semicomplete digraphs. SIAM J. Discrete Math.\u00a01(3), 281\u2013298 (1988)","journal-title":"SIAM J. Discrete Math."},{"issue":"5","key":"70_CR2","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":"1","key":"70_CR3","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/s10601-008-9054-z","volume":"14","author":"M. Bodirsky","year":"2009","unstructured":"Bodirsky, M., Chen, H.: Relatively quantified constraint satisfaction. Constraints\u00a014(1), 3\u201315 (2009)","journal-title":"Constraints"},{"issue":"8","key":"70_CR4","doi-asserted-by":"publisher","first-page":"3682","DOI":"10.1137\/080725209","volume":"39","author":"M. Bodirsky","year":"2010","unstructured":"Bodirsky, M., Chen, H.: Quantified equality constraints. SIAM J. Comput.\u00a039(8), 3682\u20133699 (2010)","journal-title":"SIAM J. Comput."},{"key":"#cr-split#-70_CR5.1","doi-asserted-by":"crossref","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-944 (2009)","DOI":"10.1016\/j.ic.2009.05.003"},{"key":"#cr-split#-70_CR5.2","unstructured":"Technical report \"Quantified Constraints and Surjective Polymorphisms\" was 2002 and Conference Version \"Quantified Constraints: Algorithms and Complexity\" was CSL 2003 (2003)"},{"issue":"1","key":"70_CR6","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":"70_CR7","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"},{"key":"70_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1007\/978-3-642-20712-9_14","volume-title":"Computer Science \u2013 Theory and Applications","author":"C. Carvalho","year":"2011","unstructured":"Carvalho, C., Egri, L., Jackson, M., Niven, T.: On maltsev digraphs. In: Kulikov, A., Vereshchagin, N. (eds.) CSR 2011. LNCS, vol.\u00a06651, pp. 181\u2013194. Springer, Heidelberg (2011)"},{"key":"70_CR9","doi-asserted-by":"crossref","unstructured":"Chen, H.: Meditations on quantified constraint satisfaction. In: Constable, R.L., Silva, A. (eds.) Kozen Festschrift. LNCS, vol.\u00a07230, pp. 35\u201349. Springer, Heidelberg (2012)","DOI":"10.1007\/978-3-642-29485-3_4"},{"issue":"1","key":"70_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":"70_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":"70_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":"70_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1007\/978-3-540-92800-3_6","volume-title":"Complexity of Constraints","author":"P.G. Kolaitis","year":"2008","unstructured":"Kolaitis, P.G., Vardi, M.Y.: A logical approach to constraint satisfaction. In: Creignou, N., Kolaitis, P.G., Vollmer, H. (eds.) Complexity of Constraints. LNCS, vol.\u00a05250, pp. 125\u2013155. Springer, Heidelberg (2008)"},{"key":"70_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"322","DOI":"10.1007\/978-3-642-38536-0_28","volume-title":"Computer Science \u2013 Theory and Applications","author":"F. Madelaine","year":"2013","unstructured":"Madelaine, F., Martin, B.: Qcsp on partially reflexive cycles - the wavy line of tractability. In: Bulatov, A.A., Shur, A.M. (eds.) CSR 2013. LNCS, vol.\u00a07913, pp. 322\u2013333. Springer, Heidelberg (2013)"},{"key":"70_CR15","unstructured":"Martin, B.: Logic, Computation and Constraint Satisfaction. PhD thesis, University of Leicester (2006)"},{"key":"70_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":"70_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":"70_CR18","unstructured":"Papadimitriou, C.H.: Computational Complexity. Addison-Wesley (1994)"},{"key":"70_CR19","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","Automata, Languages, and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-43948-7_70","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,26]],"date-time":"2019-05-26T22:09:18Z","timestamp":1558908558000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-43948-7_70"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783662439470","9783662439487"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-43948-7_70","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}