{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,12,21]],"date-time":"2023-12-21T19:37:10Z","timestamp":1703187430693},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2014,11,6]],"date-time":"2014-11-06T00:00:00Z","timestamp":1415232000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["comput. complex."],"published-print":{"date-parts":[[2016,12]]},"DOI":"10.1007\/s00037-014-0093-0","type":"journal-article","created":{"date-parts":[[2014,11,5]],"date-time":"2014-11-05T09:07:49Z","timestamp":1415178469000},"page":"737-773","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Testing list H-homomorphisms"],"prefix":"10.1007","volume":"25","author":[{"given":"Yuichi","family":"Yoshida","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2014,11,6]]},"reference":[{"issue":"1","key":"93_CR1","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1137\/060667177","volume":"39","author":"N. Alon","year":"2009","unstructured":"Alon N., Fischer E., Newman I., Shapira A. (2009) A Combinatorial Characterization of the Testable Graph Properties: It\u2019s All About Regularity. SIAM Journal on Computing 39(1): 143\u2013167","journal-title":"SIAM Journal on Computing"},{"key":"93_CR2","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1016\/S0196-6774(03)00019-1","volume":"47","author":"N. Alon","year":"2003","unstructured":"Alon N., Shapira A. (2003) Testing satisfiability. Journal of Algorithms 47: 87\u2013103","journal-title":"Journal of Algorithms"},{"key":"93_CR3","doi-asserted-by":"crossref","unstructured":"L. Barto (2011). The Dichotomy for Conservative Constraint Satisfaction Problems Revisited. In Proceedings of the 26th Annual IEEE Symposium on Logic in Computer Science (LICS), 301\u2013310.","DOI":"10.1109\/LICS.2011.25"},{"issue":"1","key":"93_CR4","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1137\/S0097539704445445","volume":"35","author":"E. Ben-Sasson","year":"2006","unstructured":"Ben-Sasson E., Harsha P., Raskhodnikova S. (2006) Some 3CNF Properties are Hard to Test. SIAM Journal on Computing 35(1): 1\u201321","journal-title":"SIAM Journal on Computing"},{"key":"93_CR5","doi-asserted-by":"crossref","unstructured":"A. Bhattacharyya, E. Grigorescu & A. Shapira (2010). A Unified Framework for Testing Linear-Invariant Properties. In Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS), 478\u2013487.","DOI":"10.1109\/FOCS.2010.53"},{"key":"93_CR6","doi-asserted-by":"crossref","unstructured":"A. Bhattacharyya & Y. Yoshida (2013). An Algebraic Characterization of Testable Boolean CSPs. In Proceedings of the 40th International Colloquium on Automata, Languages, and Programming (ICALP), 123\u2013134.","DOI":"10.1007\/978-3-642-39206-1_11"},{"issue":"3","key":"93_CR7","first-page":"87","volume":"5","author":"V. Bodnarchuk","year":"1969","unstructured":"Bodnarchuk V., Kaluzhnin L., Kotov V., Romov B. (1969) Galois theory for post algebras. I. Cybernetics and Systems Analysis 5(3): 87\u2013103","journal-title":"Cybernetics and Systems Analysis"},{"issue":"5","key":"93_CR8","first-page":"531","volume":"5","author":"V. Bodnarchuk","year":"1969","unstructured":"Bodnarchuk V., Kaluzhnin L., Kotov V. N., Romov B. A. (1969) Galois theory for Post algebras. II. Cybernetics and Systems Analysis 5(5): 531\u2013539","journal-title":"Cybernetics and Systems Analysis"},{"key":"93_CR9","doi-asserted-by":"crossref","unstructured":"R. Brewster, T. Feder, P. Hell, J. Huang & G. MacGillivray (2008). Near-Unanimity Functions and Varieties of Reflexive Graphs. SIAM Journal of Discrete Math 22(3), 938\u2013960.","DOI":"10.1137\/S0895480103436748"},{"key":"93_CR10","doi-asserted-by":"crossref","unstructured":"A. Bulatov (2003). Tractable Conservative Constraint Satisfaction Problems. InProceedings of the 18th Annual IEEE Symposium on Logic in Computer Science (LICS), 321\u2013330.","DOI":"10.1109\/LICS.2003.1210072"},{"issue":"1","key":"93_CR11","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1016\/j.tcs.2005.09.028","volume":"349","author":"A. Bulatov","year":"2005","unstructured":"Bulatov A. (2005) H-Coloring Dichotomy Revisited. Theoretical Computer Science 349(1): 31\u201339","journal-title":"Theoretical Computer Science"},{"issue":"2","key":"93_CR12","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1016\/j.jalgebra.2004.07.044","volume":"298","author":"A. Bulatov","year":"2006","unstructured":"Bulatov A. (2006) Combinatorial Problems Raised from 2- Semilattices. Journal of Algebra 298(2): 321\u2013339","journal-title":"Journal of Algebra"},{"key":"93_CR13","unstructured":"A. Bulatov & P. Jeavons (2001). Algebraic structures in combinatorial problems. Technical Report MATH-AL-4-2001, TU Dresden."},{"key":"93_CR14","doi-asserted-by":"crossref","unstructured":"A. Bulatov & M. Valeriote (2008). Recent Results on the Algebraic Approach to the CSP. Complexity of Constraints 68\u201392.","DOI":"10.1007\/978-3-540-92800-3_4"},{"key":"93_CR15","doi-asserted-by":"crossref","unstructured":"Andrei A Bulatov & V\u00edctor Dalmau (2007). Towards a dichotomy theorem for the counting constraint satisfaction problem. Information and Computation 205(5), 651\u2013678.","DOI":"10.1016\/j.ic.2006.09.005"},{"key":"93_CR16","doi-asserted-by":"crossref","unstructured":"S. Chakraborty, E. Fischer, O. Lachish, A. Matsliah & I. Newman (2007). Testing st-Connectivity. 380\u2013394.","DOI":"10.1007\/978-3-540-74208-1_28"},{"key":"93_CR17","unstructured":"K. Denecke & S. Wismath (2002). Universal algebra and applications in theoretical computer science. CRC Press."},{"issue":"2","key":"93_CR18","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1007\/s00224-011-9333-8","volume":"51","author":"L. Egri","year":"2012","unstructured":"Egri L., Krokhin A., Larose B., Tesson P. (2012) The Complexity of the List Homomorphism Problem for Graphs. Theory of Computing Systems 51(2): 143\u2013178","journal-title":"Theory of Computing Systems"},{"key":"93_CR19","doi-asserted-by":"crossref","unstructured":"T. Feder & P. Hell (1998). List Homomorphisms to Reflexive Graphs. Journal of Combinatorial Theory, Series B 72(2), 236\u2013250.","DOI":"10.1006\/jctb.1997.1812"},{"key":"93_CR20","doi-asserted-by":"crossref","unstructured":"T. Feder, P. Hell & J. Huang (1999). List Homomorphisms and Circular Arc Graphs. Combinatorica 19(4), 487\u2013505.","DOI":"10.1007\/s004939970003"},{"key":"93_CR21","doi-asserted-by":"crossref","unstructured":"T. Feder, P. Hell & J. Huang (2003). Bi-arc Graphs and the Complexity of List Homomorphisms. Journal of Graph Theory 42(1), 61\u201380.","DOI":"10.1002\/jgt.10073"},{"key":"93_CR22","doi-asserted-by":"crossref","unstructured":"T. Feder & M. Vardi (1998). The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory. SIAM Journal of Computing 28(1), 57\u2013 104.","DOI":"10.1137\/S0097539794266766"},{"key":"93_CR23","doi-asserted-by":"crossref","unstructured":"E. Fischer, O. Lachish, A. Matsliah, I. Newman & O. Yahalom (2012). On the query complexity of testing orientations for being Eulerian. ACM Transactions on Algorithms 8(2), 15.","DOI":"10.1145\/2151171.2151178"},{"key":"93_CR24","doi-asserted-by":"crossref","unstructured":"E. Fischer, E. Lehman, I. Newman, S. Raskhodnikova, R. Rubinfeld & A. Samorodnitsky (2002). Monotonicity Testing over General Poset Domains. In Proceedings of the 34th Annual ACM Symposium on Theory of computing (STOC), 474\u2013483.","DOI":"10.1145\/509907.509977"},{"key":"93_CR25","doi-asserted-by":"crossref","unstructured":"O. Goldreich (2011). Introduction to Testing Graph Properties. Property testing 105\u2013141.","DOI":"10.1007\/978-3-642-16367-8"},{"issue":"4","key":"93_CR26","doi-asserted-by":"crossref","first-page":"653","DOI":"10.1145\/285055.285060","volume":"45","author":"O. Goldreich","year":"1998","unstructured":"Goldreich O., Goldwasser S., Ron D. (1998) Property Testing and its Connection to Learning and Approximation. Journal of the ACM 45(4): 653\u2013750","journal-title":"Journal of the ACM"},{"issue":"3","key":"93_CR27","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1007\/s004930050060","volume":"19","author":"O. Goldreich","year":"1999","unstructured":"Goldreich O., Ron D. (1999) A Sublinear Bipartiteness Tester for Bounded Degree Graphs. Combinatorica 19(3): 335\u2013373","journal-title":"Combinatorica"},{"key":"93_CR28","doi-asserted-by":"crossref","unstructured":"O. Goldreich & D. Ron (2002). Property Testing in Bounded Degree Graphs. Algorithmica 32(2), 302\u2013343.","DOI":"10.1007\/s00453-001-0078-7"},{"key":"93_CR29","doi-asserted-by":"crossref","unstructured":"P. Hell & J. Ne\u0161et\u0159il (1990). On the Complexity of H-Coloring. Journal of Combinatorial Theory, Series B 48(1), 92\u2013110.","DOI":"10.1016\/0095-8956(90)90132-J"},{"key":"93_CR30","doi-asserted-by":"crossref","unstructured":"P. Hell & J. Ne\u0161et\u0159il (2004). Counting List Homomorphisms for Graphs with Bounded Degrees. In Graphs, Morphisms, and Statistical Physics: DIMACS Workshop Graphs, Morphisms and Statistical Physics, volume 63, 105. American Mathematical Society.","DOI":"10.1090\/dimacs\/063\/08"},{"key":"93_CR31","doi-asserted-by":"crossref","unstructured":"D. Hobby & R. McKenzie (1988). The structure of finite algebras. American Mathematical Society.","DOI":"10.1090\/conm\/076"},{"issue":"4","key":"93_CR32","doi-asserted-by":"crossref","first-page":"527","DOI":"10.1145\/263867.263489","volume":"44","author":"P. Jeavons","year":"1997","unstructured":"Jeavons P., Cohen D., Gyssens M. (1997) Closure Properties of Constraints. Journal of the ACM 44(4): 527\u2013548","journal-title":"Journal of the ACM"},{"key":"93_CR33","doi-asserted-by":"crossref","unstructured":"T. Kaufman & M. Sudan (2008). Algebraic Property Testing: the Role of Invariance. In Proceedings of the 40th Annual ACM Symposium on Theory of computing (STOC), 403\u2013412.","DOI":"10.1145\/1374376.1374434"},{"key":"93_CR34","doi-asserted-by":"crossref","unstructured":"I. Newman (2010). Property Testing of Massively Parametrized Problems - a survey. In Property Testing, volume 6390 of LNCS, 142\u2013157. Springer.","DOI":"10.1007\/978-3-642-16367-8_8"},{"issue":"2","key":"93_CR35","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1561\/0400000029","volume":"5","author":"D. Ron","year":"2009","unstructured":"Ron D. (2009) Algorithmic and Analysis Techniques in Property Testing. Foundations and Trends in Theoretical Computer Science 5(2): 73\u2013205","journal-title":"Foundations and Trends in Theoretical Computer Science"},{"key":"93_CR36","doi-asserted-by":"crossref","unstructured":"C. Sohler (2012). Almost Optimal Canonical Property Testers for Satisfiability. In Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS), 541\u2013550.","DOI":"10.1109\/FOCS.2012.59"},{"key":"93_CR37","doi-asserted-by":"crossref","unstructured":"Y. Yoshida (2011). Optimal Constant-Time Approximation Algorithms and (Unconditional) Inapproximability Results for Every Bounded-Degree CSP. In Proceedings of the 43rd Annual ACM Symposium on Theory of computing (STOC), 665\u2013674.","DOI":"10.1145\/1993636.1993725"},{"key":"93_CR38","doi-asserted-by":"crossref","first-page":"98","DOI":"10.1016\/j.tcs.2012.01.045","volume":"434","author":"Y. YoshidaY. Kobayashi","year":"2012","unstructured":"YoshidaY. Kobayashi Y. (2012) Testing (s,t)-Disconnectivity of Graphs and Digraphs. Theoretical Computer Science 434: 98\u2013113","journal-title":"Theoretical Computer Science"}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-014-0093-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00037-014-0093-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-014-0093-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-014-0093-0","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,22]],"date-time":"2019-05-22T15:01:58Z","timestamp":1558537318000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00037-014-0093-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,11,6]]},"references-count":38,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2016,12]]}},"alternative-id":["93"],"URL":"https:\/\/doi.org\/10.1007\/s00037-014-0093-0","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,11,6]]}}}