{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,12,13]],"date-time":"2023-12-13T08:05:05Z","timestamp":1702454705767},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2011,5,19]],"date-time":"2011-05-19T00:00:00Z","timestamp":1305763200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2012,8]]},"DOI":"10.1007\/s00224-011-9333-8","type":"journal-article","created":{"date-parts":[[2011,5,18]],"date-time":"2011-05-18T05:39:58Z","timestamp":1305697198000},"page":"143-178","source":"Crossref","is-referenced-by-count":12,"title":["The Complexity of the List Homomorphism Problem for Graphs"],"prefix":"10.1007","volume":"51","author":[{"given":"L\u00e1szl\u00f3","family":"Egri","sequence":"first","affiliation":[]},{"given":"Andrei","family":"Krokhin","sequence":"additional","affiliation":[]},{"given":"Benoit","family":"Larose","sequence":"additional","affiliation":[]},{"given":"Pascal","family":"Tesson","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2011,5,19]]},"reference":[{"issue":"4","key":"9333_CR1","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1016\/j.jcss.2008.11.001","volume":"75","author":"E. Allender","year":"2009","unstructured":"Allender, E., Bauland, M., Immerman, N., Schnoor, H., Vollmer, H.: The complexity of satisfiability problems: Refining Schaefer\u2019s theorem. J. Comput. Syst. Sci. 75(4), 245\u2013254 (2009)","journal-title":"J. Comput. Syst. Sci."},{"key":"9333_CR2","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511804090","volume-title":"Computational Complexity: A Modern Approach","author":"S. Arora","year":"2009","unstructured":"Arora, S., Barak, B.: Computational Complexity: A Modern Approach. Cambridge University Press, Cambridge (2009)"},{"key":"9333_CR3","doi-asserted-by":"crossref","first-page":"595","DOI":"10.1109\/FOCS.2009.32","volume-title":"Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS\u201909","author":"L. Barto","year":"2009","unstructured":"Barto, L., Kozik, M.: Constraint satisfaction problems of bounded width. In: Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS\u201909, pp.\u00a0595\u2013603 (2009)"},{"issue":"5","key":"9333_CR4","doi-asserted-by":"crossref","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\u00a0positive answer to a conjecture of Bang-Jensen and Hell). SIAM J. Comput. 38(5), 1782\u20131802 (2009)","journal-title":"SIAM J. Comput."},{"key":"9333_CR5","doi-asserted-by":"crossref","first-page":"938","DOI":"10.1137\/S0895480103436748","volume":"22","author":"R. Brewster","year":"2008","unstructured":"Brewster, R., Feder, T., Hell, P., Huang, J., MacGillavray, G.: Near-unanimity functions and varieties of reflexive graphs. SIAM J. Discrete Math. 22, 938\u2013960 (2008)","journal-title":"SIAM J. Discrete Math."},{"key":"9333_CR6","first-page":"321","volume-title":"LICS\u201903","author":"A. Bulatov","year":"2003","unstructured":"Bulatov, A.: Tractable conservative constraint satisfaction problems. In: LICS\u201903, pp.\u00a0321\u2013330 (2003)"},{"key":"9333_CR7","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1007\/978-3-540-92800-3_4","volume-title":"Complexity of Constraints","author":"A. Bulatov","year":"2008","unstructured":"Bulatov, A., Valeriote, M.: Recent results on the algebraic approach to the CSP. In: Complexity of Constraints. LNCS, vol.\u00a05250, pp.\u00a068\u201392 (2008)"},{"issue":"3","key":"9333_CR8","doi-asserted-by":"crossref","first-page":"720","DOI":"10.1137\/S0097539700376676","volume":"34","author":"A. Bulatov","year":"2005","unstructured":"Bulatov, A., Jeavons, P., Krokhin, A.: Classifying complexity of constraints using finite algebras. SIAM J. Comput. 34(3), 720\u2013742 (2005)","journal-title":"SIAM J. Comput."},{"key":"9333_CR9","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1007\/978-3-540-92800-3_5","volume-title":"Complexity of Constraints","author":"A. Bulatov","year":"2008","unstructured":"Bulatov, A., Krokhin, A., Larose, B.: Dualities for constraint satisfaction problems. In: Complexity of Constraints. LNCS, vol.\u00a05250, pp.\u00a093\u2013124 (2008)"},{"key":"9333_CR10","first-page":"307","volume-title":"LICS\u201908","author":"C. Carvalho","year":"2008","unstructured":"Carvalho, C., Dalmau, V., Krokhin, A.: Caterpillar duality for constraint satisfaction problems. In: LICS\u201908, pp.\u00a0307\u2013316 (2008)"},{"issue":"34\u201336","key":"9333_CR11","doi-asserted-by":"crossref","first-page":"3188","DOI":"10.1016\/j.tcs.2010.05.016","volume":"411","author":"C. Carvalho","year":"2010","unstructured":"Carvalho, C., Dalmau, V., Krokhin, A.: CSP duality and trees of bounded pathwidth. Theor. Comput. Sci. 411(34\u201336), 3188\u20133208 (2010)","journal-title":"Theor. Comput. Sci."},{"key":"9333_CR12","volume-title":"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.) Handbook of Constraint Programming. Elsevier, Amsterdam (2006). Chap.\u00a08"},{"key":"9333_CR13","doi-asserted-by":"crossref","unstructured":"Dalmau, V.: Linear Datalog and bounded path duality for relational structures. Log. Methods Comput. Sci. 1(1) (2005). (Electronic)","DOI":"10.2168\/LMCS-1(1:5)2005"},{"issue":"4","key":"9333_CR14","doi-asserted-by":"crossref","first-page":"821","DOI":"10.1016\/j.ejc.2007.11.020","volume":"29","author":"V. Dalmau","year":"2008","unstructured":"Dalmau, V., Krokhin, A.: Majority constraints have bounded pathwidth duality. Eur. J. Comb. 29(4), 821\u2013837 (2008)","journal-title":"Eur. J. Comb."},{"key":"9333_CR15","first-page":"297","volume-title":"LICS\u201908","author":"V. Dalmau","year":"2008","unstructured":"Dalmau, V., Larose, B.: Maltsev + Datalog \u21d2 Symmetric Datalog. In: LICS\u201908, pp.\u00a0297\u2013306 (2008)"},{"key":"9333_CR16","first-page":"193","volume-title":"LICS\u201907","author":"L. Egri","year":"2007","unstructured":"Egri, L., Larose, B., Tesson, P.: Symmetric Datalog and constraint satisfaction problems in Logspace. In: LICS\u201907, pp.\u00a0193\u2013202 (2007)"},{"key":"9333_CR17","doi-asserted-by":"crossref","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 J. Comput. 28, 57\u2013104 (1998)","journal-title":"SIAM J. Comput."},{"key":"9333_CR18","doi-asserted-by":"crossref","first-page":"487","DOI":"10.1007\/s004939970003","volume":"19","author":"T. Feder","year":"1999","unstructured":"Feder, T., Hell, P., Huang, J.: List homomorphisms and circular arc graphs. Combinatorica 19, 487\u2013505 (1999)","journal-title":"Combinatorica"},{"key":"9333_CR19","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1002\/jgt.10073","volume":"42","author":"T. Feder","year":"2003","unstructured":"Feder, T., Hell, P., Huang, J.: Bi-arc graphs and the complexity of list homomorphisms. J. Graph Theory 42, 61\u201380 (2003)","journal-title":"J. Graph Theory"},{"issue":"2","key":"9333_CR20","doi-asserted-by":"crossref","first-page":"271","DOI":"10.1016\/j.disc.2005.11.014","volume":"306","author":"F. Gurski","year":"2006","unstructured":"Gurski, F.: Characterizations of co-graphs defined by restricted NLC-width or clique-width operations. Discrete Math. 306(2), 271\u2013277 (2006)","journal-title":"Discrete Math."},{"key":"9333_CR21","doi-asserted-by":"crossref","DOI":"10.1093\/acprof:oso\/9780198528173.001.0001","volume-title":"Graphs and Homomorphisms","author":"P. Hell","year":"2004","unstructured":"Hell, P., Ne\u0161et\u0159il, J.: Graphs and Homomorphisms. Oxford University Press, London (2004)"},{"key":"9333_CR22","doi-asserted-by":"crossref","DOI":"10.1090\/conm\/076","volume-title":"The Structure of Finite Algebras","author":"D. Hobby","year":"1988","unstructured":"Hobby, D., McKenzie, R.N.: The Structure of Finite Algebras. AMS, Providence (1988)"},{"key":"9333_CR23","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1007\/978-3-540-92800-3_6","volume-title":"Complexity of Constraints","author":"Ph.G. Kolaitis","year":"2008","unstructured":"Kolaitis, Ph.G., Vardi, M.Y.: A logical approach to constraint satisfaction. In: Complexity of Constraints. LNCS, vol.\u00a05250, pp.\u00a0125\u2013155 (2008)"},{"issue":"18","key":"9333_CR24","doi-asserted-by":"crossref","first-page":"1629","DOI":"10.1016\/j.tcs.2008.12.048","volume":"410","author":"B. Larose","year":"2009","unstructured":"Larose, B., Tesson, P.: Universal algebra and hardness results for constraint satisfaction problems. Theor. Comput. Sci. 410(18), 1629\u20131647 (2009)","journal-title":"Theor. Comput. Sci."},{"issue":"3\u20134","key":"9333_CR25","doi-asserted-by":"crossref","first-page":"439","DOI":"10.1007\/s00012-007-2012-6","volume":"56","author":"B. Larose","year":"2007","unstructured":"Larose, B., Z\u00e1dori, L.: Bounded width problems and algebras. Algebra Univers. 56(3\u20134), 439\u2013466 (2007)","journal-title":"Algebra Univers."},{"key":"9333_CR26","doi-asserted-by":"crossref","unstructured":"Larose, B., Loten, C., Tardif, C.: A characterisation of first-order constraint satisfaction problems. Log. Methods Comput. Sci. 3(4) (2007). (Electronic)","DOI":"10.2168\/LMCS-3(4:6)2007"},{"issue":"3\u20134","key":"9333_CR27","doi-asserted-by":"crossref","first-page":"463","DOI":"10.1007\/s00012-008-2122-9","volume":"59","author":"M. Mar\u00f3ti","year":"2008","unstructured":"Mar\u00f3ti, M., McKenzie, R.: Existence theorems for weakly symmetric operations. Algebra Univers. 59(3\u20134), 463\u2013489 (2008)","journal-title":"Algebra Univers."},{"issue":"2","key":"9333_CR28","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1007\/s00453-003-1032-7","volume":"37","author":"R. McConnell","year":"2003","unstructured":"McConnell, R.: Linear-time recognition of circular-arc graphs. Algorithmica 37(2), 93\u2013147 (2003)","journal-title":"Algorithmica"},{"key":"9333_CR29","volume-title":"Algebras, Lattices and Varieties","author":"R.N. McKenzie","year":"1987","unstructured":"McKenzie, R.N., McNulty, G.F., Taylor, W.F.: Algebras, Lattices and Varieties, vol.\u00a0I. Wadsworth & Brooks, Pacific Grove (1987)"},{"key":"9333_CR30","volume-title":"Computational Complexity","author":"C.H. Papadimitriou","year":"1994","unstructured":"Papadimitriou, C.H.: Computational Complexity. Addison-Wesley, Reading (1994)"},{"key":"9333_CR31","first-page":"216","volume-title":"STOC\u201978","author":"T.J. Schaefer","year":"1978","unstructured":"Schaefer, T.J.: The complexity of satisfiability problems. In: STOC\u201978, pp.\u00a0216\u2013226 (1978)"},{"issue":"2","key":"9333_CR32","doi-asserted-by":"crossref","first-page":"451","DOI":"10.4153\/CJM-2009-023-2","volume":"61","author":"M. Valeriote","year":"2009","unstructured":"Valeriote, M.: A subalgebra intersection property for congruence-distributive varieties. Can. J. Math. 61(2), 451\u2013464 (2009)","journal-title":"Can. J. Math."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-011-9333-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-011-9333-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-011-9333-8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,10]],"date-time":"2019-06-10T21:46:53Z","timestamp":1560203213000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-011-9333-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,5,19]]},"references-count":32,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2012,8]]}},"alternative-id":["9333"],"URL":"https:\/\/doi.org\/10.1007\/s00224-011-9333-8","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,5,19]]}}}