{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T00:47:32Z","timestamp":1725497252569},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540771180"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-77120-3_55","type":"book-chapter","created":{"date-parts":[[2007,12,6]],"date-time":"2007-12-06T11:31:09Z","timestamp":1196940669000},"page":"632-643","source":"Crossref","is-referenced-by-count":4,"title":["Bounded Tree-Width and CSP-Related Problems"],"prefix":"10.1007","author":[{"given":"Tommy","family":"F\u00e4rnqvist","sequence":"first","affiliation":[]},{"given":"Peter","family":"Jonsson","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"55_CR1","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-58412-1","volume-title":"Complexity and approximation: Combinatorial optimization problems and their approximability properties","author":"G. Ausiello","year":"1999","unstructured":"Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Marchetti, A.: Complexity and approximation: Combinatorial optimization problems and their approximability properties. Springer, Heidelberg (1999)"},{"unstructured":"Bulatov, A.A.: Tractable conservative constraint satisfaction problems. ACM Transactions on Computational Logic (to appear)","key":"55_CR2"},{"issue":"1-3","key":"55_CR3","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1016\/j.tcs.2004.08.008","volume":"329","author":"V. Dalmau","year":"2004","unstructured":"Dalmau, V., Jonsson, P.: The complexity of counting homomorphisms seen from the other side. Theoretical Computer Science\u00a0329(1-3), 315\u2013323 (2004)","journal-title":"Theoretical Computer Science"},{"key":"55_CR4","doi-asserted-by":"publisher","first-page":"873","DOI":"10.1137\/S0097539792228228","volume":"24","author":"R.G. Downey","year":"1995","unstructured":"Downey, R.G., Fellows, M.R.: Fixed-parameter tractability and completeness I: Basic results. SIAM Journal on Computing\u00a024, 873\u2013921 (1995)","journal-title":"SIAM Journal on Computing"},{"key":"55_CR5","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/0304-3975(94)00097-3","volume":"141","author":"R.G. Downey","year":"1995","unstructured":"Downey, R.G., Fellows, M.R.: Fixed-parameter tractability and completeness II: On completeness for W[1]. Theoretical Computer Science\u00a0141, 109\u2013131 (1995)","journal-title":"Theoretical Computer Science"},{"key":"55_CR6","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 Series B\u00a072, 236\u2013250 (1998)","journal-title":"J. Comb. Theory Series B"},{"key":"55_CR7","doi-asserted-by":"publisher","first-page":"230","DOI":"10.1137\/S0097539703427197","volume":"36","author":"T. Feder","year":"2006","unstructured":"Feder, T., Hell, P.: Full constraint satisfaction problems. SIAM Journal on Computing\u00a036, 230\u2013246 (2006)","journal-title":"SIAM Journal on Computing"},{"unstructured":"Feder, T., Hell, P.: Edge list homomorphisms, manuscript","key":"55_CR8"},{"key":"55_CR9","doi-asserted-by":"publisher","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\u00a019, 487\u2013505 (1999)","journal-title":"Combinatorica"},{"key":"55_CR10","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1002\/jgt.10073","volume":"42","author":"T. Feder","year":"1999","unstructured":"Feder, T., Hell, P., Huang, J.: Bi-arc graphs and the complexity of list homomorphisms. J. Graph Theory\u00a042, 61\u201380 (1999)","journal-title":"J. Graph Theory"},{"unstructured":"Feder, T., Hell, P., Huang, J.: List homomorphisms to reflexive digraphs, manuscript (2005)","key":"55_CR11"},{"unstructured":"Feder, T., Hell, P., Huang, J.: List homomorphisms of graphs with bounded degree. in Discrete Math (to appear)","key":"55_CR12"},{"issue":"1","key":"55_CR13","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(1), 57\u2013104 (1998)","journal-title":"SIAM Journal on Computing"},{"doi-asserted-by":"crossref","unstructured":"Flum, J., Grohe, M.: The parameterized complexity of counting problems. In: Proceedings of the 43rd IEEE Symposium on Foundations of Computer Science, pp. 538\u2013547 (2002)","key":"55_CR14","DOI":"10.1109\/SFCS.2002.1181978"},{"issue":"1","key":"55_CR15","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1206035.1206036","volume":"54","author":"M. Grohe","year":"2007","unstructured":"Grohe, M.: The complexity of homomorphism and constraint satisfaction problems seen from the other side. Journal of the ACM\u00a054(1), 1\u201324 (2007)","journal-title":"Journal of the ACM"},{"key":"55_CR16","doi-asserted-by":"publisher","first-page":"881","DOI":"10.1016\/j.dam.2005.06.012","volume":"154","author":"G. Gutin","year":"2006","unstructured":"Gutin, G., Rafiey, A., Yeo, A., Tso, M.: Level of repair analysis and minimum cost homomorphisms of graphs. Discrete Appl. Math.\u00a0154, 881\u2013889 (2006)","journal-title":"Discrete Appl. Math."},{"key":"55_CR17","series-title":"London Math. Society Lecture Note Series","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1017\/CBO9781107359970.008","volume-title":"Survey in combinatorics 2003","author":"P. Hell","year":"2003","unstructured":"Hell, P.: Algorithmic aspects of graph homomorphisms. In: Survey in combinatorics 2003. London Math. Society Lecture Note Series, vol.\u00a0307, pp. 239\u2013276. Cambridge University Press, Cambridge (2003)"},{"doi-asserted-by":"crossref","unstructured":"Hell, P., Nes\u0306etr\u0306il, J.: Counting list homomorphisms for graphs with bounded degree. Graphs, morphisms and statistical physics, DIMACS Series in Discrete Mathematics and Theoretical Computer Science 63, 105\u2013112 (2004)","key":"55_CR18","DOI":"10.1090\/dimacs\/063\/08"},{"doi-asserted-by":"crossref","unstructured":"Hicks, I., Koster, A., Koloto\u011flu, E.: Branch and tree decomposition techniques for discrete optimization. In: TutORials 2005. INFORMS TutORials in Operations Research Series, pp. 1\u201329 (2005)","key":"55_CR19","DOI":"10.1287\/educ.1053.0017"},{"issue":"1\u20132","key":"55_CR20","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(1\u20132), 185\u2013204 (1998)","journal-title":"Theoretical Computer Science"},{"doi-asserted-by":"crossref","unstructured":"Jonsson, P., Nordh, G.: Generalised integer programming based on logically defined relations. In: Proceedings of the 31st International Symposium on Mathematical Foundations of Computer Science, pp. 549\u2013560 (2006)","key":"55_CR21","DOI":"10.1007\/11821069_48"},{"issue":"6","key":"55_CR22","doi-asserted-by":"publisher","first-page":"1863","DOI":"10.1137\/S0097539799349948","volume":"30","author":"S. Khanna","year":"2001","unstructured":"Khanna, S., Sudan, M., Trevisan, L., Williamson, D.P.: The approximability of constraint satisfaction problems. SIAM Journal on Computing\u00a030(6), 1863\u20131920 (2001)","journal-title":"SIAM Journal on Computing"},{"key":"55_CR23","doi-asserted-by":"publisher","first-page":"302","DOI":"10.1006\/jcss.2000.1713","volume":"61","author":"P.G. Kolaitis","year":"2000","unstructured":"Kolaitis, P.G., Vardi, M.: Conjunctive-query containment and constraint satisfaction. Journal of Computer and System Sciences\u00a061, 302\u2013332 (2000)","journal-title":"Journal of Computer and System Sciences"},{"doi-asserted-by":"crossref","unstructured":"Kroon, L.G., Sen, A., Deng, H., Roy, A.: The optimal cost chromatic partition problem for trees and interval graphs. In: Graph-Theoretic Concepts in Computer Science, pp. 279\u2013292 (1997)","key":"55_CR24","DOI":"10.1007\/3-540-62559-3_23"},{"key":"55_CR25","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1006\/jctb.1994.1073","volume":"62","author":"N. Robertson","year":"1994","unstructured":"Robertson, N., Seymour, P.: Graph minors V: Excluding a planar graph. Journal of Combinatorial Theory, ser. B\u00a062, 323\u2013348 (1994)","journal-title":"Journal of Combinatorial Theory, ser. B"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-77120-3_55.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T11:01:20Z","timestamp":1619521280000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-77120-3_55"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540771180"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-77120-3_55","relation":{},"subject":[]}}