{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,4]],"date-time":"2022-04-04T11:56:56Z","timestamp":1649073416936},"reference-count":42,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2015,2,19]],"date-time":"2015-02-19T00:00:00Z","timestamp":1424304000000},"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":["Constraints"],"published-print":{"date-parts":[[2016,4]]},"DOI":"10.1007\/s10601-015-9181-2","type":"journal-article","created":{"date-parts":[[2015,2,18]],"date-time":"2015-02-18T02:53:29Z","timestamp":1424228009000},"page":"198-222","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Structural decompositions for problems with global constraints"],"prefix":"10.1007","volume":"21","author":[{"given":"Evgenij","family":"Thorstensen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,2,19]]},"reference":[{"key":"9181_CR1","unstructured":"Adler, I. (2006). Width functions for hypertree decompositions. Doctoral dissertation, Albert-Ludwigs-Universit\u00e4t Freiburg."},{"issue":"8","key":"9181_CR2","doi-asserted-by":"crossref","first-page":"2167","DOI":"10.1016\/j.ejc.2007.04.013","volume":"28","author":"I Adler","year":"2007","unstructured":"Adler, I., Gottlob, G., Grohe, M. (2007). Hypertree width and related hypergraph invariants. European Journal of Combinatorics, 28(8), 2167\u20132181. doi: 10.1016\/j.ejc.2007.04.013 . http:\/\/www.sciencedirect.com\/science\/article\/pii\/S0195669807000753 .","journal-title":"European Journal of Combinatorics"},{"key":"9181_CR3","doi-asserted-by":"crossref","unstructured":"Aschinger, M., Drescher, C., Friedrich, G., Gottlob, G., Jeavons, P., Ryabokon, A., Thorstensen, E. (2011). Optimization methods for the partner units problem. In Proceedings of the 8th International Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming for Combinatorial Optimization Problems (CPAIOR\u201911), Lecture Notes in Computer Science, (Vol. 6697 pp. 4\u201319). Berlin: Springer.","DOI":"10.1007\/978-3-642-21311-3_4"},{"key":"9181_CR4","unstructured":"Aschinger, M., Drescher, C., Gottlob, G., Jeavons, P., Thorstensen, E. (2011). Structural decomposition methods and what they are good for. In Schwentick, T., & D\u00fcrr, C. (Eds.) Proceedings of the 28th International Symposium on Theoretical Aspects of Computer Science (STACS\u201911), Leibniz International Proceedings in Informatics, (Vol. 9 pp. 12\u201328). doi: 10.4230\/LIPIcs.STACS.2011.12 . http:\/\/drops.dagstuhl.de\/opus\/volltexte\/2011\/2996 ."},{"issue":"4","key":"9181_CR5","doi-asserted-by":"crossref","first-page":"1737","DOI":"10.1137\/110859440","volume":"42","author":"A Atserias","year":"2013","unstructured":"Atserias, A., Grohe, M., Marx, D. (2013). Size bounds and query plans for relational joins. SIAM Journal on Computing, 42(4), 1737\u20131767. doi: 10.1137\/110859440 .","journal-title":"SIAM Journal on Computing"},{"issue":"2","key":"9181_CR6","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1007\/s10601-006-9007-3","volume":"12","author":"C Bessiere","year":"2007","unstructured":"Bessiere, C., Hebrard, E., Hnich, B., Walsh, T. (2007). The complexity of reasoning with global constraints. Constraints, 12(2), 239\u2013259. doi: 10.1007\/s10601-006-9007-3 .","journal-title":"Constraints"},{"key":"9181_CR7","doi-asserted-by":"crossref","unstructured":"Bessiere, C., Katsirelos, G., Narodytska, N., Quimper, C.G., Walsh, T. (2010). Decomposition of the NValue constraint. In Proceedings of the 16th International Conference on Principles and Practice of Constraint Programming (CP\u201910), Lecture Notes in Computer Science, (Vol. 6308) . Berlin: Springer.","DOI":"10.1007\/978-3-642-15396-9_12"},{"issue":"3","key":"9181_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. (2005). Classifying the complexity of constraints using finite algebras. SIAM Journal on Computing, 34(3), 720\u2013742. doi: 10.1137\/S0097539700376676 . http:\/\/link.aip.org\/link\/?SMJ\/34\/720\/1 .","journal-title":"SIAM Journal on Computing"},{"issue":"8","key":"9181_CR9","doi-asserted-by":"crossref","first-page":"847","DOI":"10.1016\/j.jcss.2010.04.003","volume":"76","author":"H Chen","year":"2010","unstructured":"Chen, H., & Grohe, M. (2010). Constraint satisfaction with succinctly specified relations. Journal of Computer and System Sciences, 76(8), 847\u2013860. doi: 10.1016\/j.jcss.2010.04.003 . http:\/\/www.sciencedirect.com\/science\/article\/pii\/S0022000010000450 .","journal-title":"Journal of Computer and System Sciences"},{"key":"9181_CR10","doi-asserted-by":"crossref","unstructured":"Cohen, D., & Green, M. (2006). Typed guarded decompositions for constraint satisfaction. In Benhamou, F. (Ed.) Proceedings of the 12th International Conference on the Principles and Practice of Constraint Programming (CP\u201906), Lecture Notes in Computer Science, (Vol. 4204 PP. 122\u2013136). Berlin: Springer. doi: 10.1007\/11889205_11 .","DOI":"10.1007\/11889205_11"},{"key":"9181_CR11","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1016\/S1574-6526(06)80012-X","volume-title":"Handbook of Constraint Programming, Foundations of Artificial Intelligence, Vol. 2","author":"D Cohen","year":"2006","unstructured":"Cohen, D., & Jeavons, P. (2006). The complexity of constraint languages In Rossi, F, Van Beek, P, Walsh, T (Eds.), Handbook of Constraint Programming, Foundations of Artificial Intelligence (Vol. 2, pp. 245\u2013280). New York: Elsevier. doi: 10.1016\/S1574-6526(06)80012-X ."},{"issue":"5","key":"9181_CR12","doi-asserted-by":"crossref","first-page":"721","DOI":"10.1016\/j.jcss.2007.08.001","volume":"74","author":"D Cohen","year":"2008","unstructured":"Cohen, D., Jeavons, P., Gyssens, M. (2008). A unified theory of structural tractability for constraint satisfaction problems. Journal of Computer and System Sciences, 74(5), 721\u2013743. doi: 10.1016\/j.jcss.2007.08.001 . http:\/\/www.sciencedirect.com\/science\/article\/pii\/S0022000007001225 .","journal-title":"Journal of Computer and System Sciences"},{"key":"9181_CR13","doi-asserted-by":"crossref","unstructured":"Cohen, D.A., Green, M.J., Houghton, C. (2009). Constraint representations and structural tractability. In Proceedings of the 15th International Conference on Principles and Practice of Constraint Programming (CP\u201909), Lecture Notes in Computer Science, (Vol. 5732. pp. 289\u2013303). Berlin: Springer.","DOI":"10.1007\/978-3-642-04244-7_24"},{"key":"9181_CR14","first-page":"230","volume-title":"Proceedings of the 19th International Conference on Principles and Practice of Constraint Programming (CP\u201913), Lecture Notes in Computer Science, Vol. 8124","author":"DA Cohen","year":"2013","unstructured":"Cohen, D.A., Jeavons, P.G., Thorstensen, E., \u017eivn\u00fd, S. (2013). Tractable combinations of global constraints In Schulte, C (Ed.), Proceedings of the 19th International Conference on Principles and Practice of Constraint Programming (CP\u201913), Lecture Notes in Computer Science (Vol. 8124, pp. 230\u2013246). Berlin: Springer."},{"key":"9181_CR15","doi-asserted-by":"crossref","unstructured":"Dalmau, V., Kolaitis, P.G., Vardi, M.Y. (2002). Constraint satisfaction, bounded treewidth, and finite-variable logics. In Proceedings of the 8th International Conference on Principles and Practice of Constraint Programming (CP\u201902), Lecture Notes in Computer Science, (Vol. 2470. pp. 223\u2013254). Berlin: Springer. http:\/\/dl.acm.org\/citation.cfm?id=647489.727145 .","DOI":"10.1007\/3-540-46135-3_21"},{"key":"9181_CR16","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized complexity. Monographs in computer science","author":"RG Downey","year":"1999","unstructured":"Downey, R.G., & Fellows, M.R. (1999). Parameterized complexity. Monographs in computer science. Berlin: Springer."},{"key":"9181_CR17","volume-title":"Parameterized complexity theory. Texts in theoretical computer science","author":"J Flum","year":"2006","unstructured":"Flum, J., & Grohe, M. (2006). Parameterized complexity theory. Texts in theoretical computer science. Berlin: Springer."},{"key":"9181_CR18","volume-title":"Computers and intractability: A guide to the theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., & Johnson, D.S. (1979). Computers and intractability: A guide to the theory of NP-Completeness. San Francisco: W. H. Freeman."},{"key":"9181_CR19","first-page":"287","volume-title":"The multivariate algorithmic revolution and beyond, Lecture Notes in Computer Science, Vol. 7370","author":"S Gaspers","year":"2012","unstructured":"Gaspers, S., & Szeider, S. (2012). Backdoors to satisfaction In Bodlaender, HL, Downey, R, Fomin, FV, Marx, D (Eds.), The multivariate algorithmic revolution and beyond, Lecture Notes in Computer Science (Vol. 7370, pp. 287\u2013317). Berlin: Springer. doi: 10.1007\/978-3-642-30891-8_15 ."},{"key":"9181_CR20","unstructured":"Gent, I.P., Jefferson, C., Miguel, I. (2006). MINION: A fast, scalable constraint solver. In Proceedings of the 17th European Conference on Artificial Intelligence (ECAI\u201906). (pp. 98\u2013102). Amsterdam: IOS Press. http:\/\/dl.acm.org\/citation.cfm?id= 1567016.1567043 ."},{"key":"9181_CR21","unstructured":"de Givry, S., Schiex, T., Verfaillie, G. (2006). Exploiting Tree Decomposition and Soft Local Consistency in Weighted CSP. In Proceedings of the 21st National Conference on Artificial Intelligence (AAAI\u201906). (pp. 22\u201327)."},{"key":"9181_CR22","volume-title":"Proceedings of the 36th International Colloquium on Automata Languages and Programming (ICALP\u201909), Lecture Notes in Computer Science, (Vol. 5556, pp. 16\u201330)","author":"G Gottlob","year":"2009","unstructured":"Gottlob, G., Greco, G., Scarcello, F. (2009). Tractable optimization problems through hypergraph-based structural restrictions In Albers, S, Marchetti-Spaccamela, A, Matias, Y, Nikoletseas, S, Thomas, W (Eds.), Proceedings of the 36th International Colloquium on Automata Languages and Programming (ICALP\u201909), Lecture Notes in Computer Science, (Vol. 5556, pp. 16\u201330). Berlin: Springer. doi: 10.1007\/978-3-642-02930-1_2 ."},{"issue":"2","key":"9181_CR23","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1016\/S0004-3702(00)00078-3","volume":"124","author":"G Gottlob","year":"2000","unstructured":"Gottlob, G., Leone, N., Scarcello, F. (2000). A comparison of structural CSP decomposition methods. Artificial Intelligence, 124(2), 243\u2013282.","journal-title":"Artificial Intelligence"},{"issue":"3","key":"9181_CR24","doi-asserted-by":"crossref","first-page":"579","DOI":"10.1006\/jcss.2001.1809","volume":"64","author":"G Gottlob","year":"2002","unstructured":"Gottlob, G., Leone, N., Scarcello, F. (2002). Hypertree decompositions and tractable queries. Journal of Computer and System Sciences, 64(3), 579\u2013627. doi: 10.1006\/jcss.2001.1809 .","journal-title":"Journal of Computer and System Sciences"},{"key":"9181_CR25","doi-asserted-by":"crossref","unstructured":"Green, M.J., & Jefferson, C. (2008). Structural tractability of propagated constraints. In Proceedings of the 14th International Conference on Principles and Practice of Constraint Programming (CP\u201908), Lecture Notes in Computer Science, (Vol. 5202. pp. 372\u2013386). Berlin: Springer. doi: 10.1007\/978-3-540-85958-1_25 .","DOI":"10.1007\/978-3-540-85958-1_25"},{"issue":"1","key":"9181_CR26","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1206035.1206036","volume":"54","author":"M Grohe","year":"2007","unstructured":"Grohe, M. (2007). The complexity of homomorphism and constraint satisfaction problems seen from the other side. Journal of the ACM, 54(1), 1\u201324. doi: 10.1145\/1206035.1206036 .","journal-title":"Journal of the ACM"},{"key":"9181_CR27","doi-asserted-by":"crossref","unstructured":"Grohe, M., & Marx, D. (2006). Constraint solving via fractional edge covers. In Proceedings of the 17th ACM-SIAM symposium on discrete algorithms (SODA\u201906). (pp. 289\u2013298): ACM. doi: 10.1145\/1109557.1109590 .","DOI":"10.1145\/1109557.1109590"},{"key":"9181_CR28","doi-asserted-by":"crossref","unstructured":"Hermenier, F., Demassey, S., Lorca, X. (2011). Bin repacking scheduling in virtualized datacenters. In Lee, J (Ed.) Proceedings of the 17th International Conference on Principles and Practice of Constraint Programming (CP\u201911), Lecture Notes in Computer Science, (Vol. 6876. pp. 27\u201341). Berlin: Springer. doi: 10.1007\/978-3-642-23786-7_5 .","DOI":"10.1007\/978-3-642-23786-7_5"},{"key":"9181_CR29","doi-asserted-by":"crossref","unstructured":"van Hoeve, W.J., & Katriel, I. (2006). Global constraints. In Rossi, F, Van Beek, P, Walsh, T (Eds.) Handbook of Constraint Programming, Foundations of Artificial Intelligence, (Vol. 2 . pp. 169\u2013208). New York: Elsevier. doi: 10.1016\/S1574-6526(06)80010-6 , http:\/\/www.sciencedirect.com\/science\/article\/B8G6H-4RXCSGY-9\/2\/4e2eda11a2a06f3925df0334d09f0e1b .","DOI":"10.1016\/S1574-6526(06)80010-6"},{"issue":"5","key":"9181_CR30","doi-asserted-by":"crossref","first-page":"884","DOI":"10.1016\/j.jcss.2008.02.001","volume":"74","author":"M Kutz","year":"2008","unstructured":"Kutz, M., Elbassioni, K., Katriel, I., Mahajan, M. (2008). Simultaneous matchings: Hardness and approximation. Journal of Computer and System Sciences, 74(5), 884\u2013897. doi: 10.1016\/j.jcss.2008.02.001 . http:\/\/portal.acm.org\/citation.cfm?id=1374847.1374923 .","journal-title":"Journal of Computer and System Sciences"},{"issue":"2","key":"9181_CR31","doi-asserted-by":"crossref","first-page":"29:1","DOI":"10.1145\/1721837.1721845","volume":"6","author":"D Marx","year":"2010","unstructured":"Marx, D. (2010). Approximating fractional hypertree width. ACM Transactions on Algorithms, 6(2), 29:1\u201329:17. doi: 10.1145\/1721837.1721845 .","journal-title":"ACM Transactions on Algorithms"},{"issue":"1","key":"9181_CR32","doi-asserted-by":"crossref","first-page":"85","DOI":"10.4086\/toc.2010.v006a005","volume":"6","author":"D Marx","year":"2010","unstructured":"Marx, D. (2010). Can you beat treewidth Theory of Computing, 6(1), 85\u2013112.","journal-title":"Theory of Computing"},{"issue":"6","key":"9181_CR33","doi-asserted-by":"crossref","first-page":"42","DOI":"10.1145\/2535926","volume":"60","author":"D Marx","year":"2013","unstructured":"Marx, D. (2013). Tractable hypergraph properties for constraint satisfaction and conjunctive queries. Journal ACM, 60(6), 42.","journal-title":"Journal ACM"},{"key":"9181_CR34","doi-asserted-by":"crossref","unstructured":"Quimper, C.G., L\u00f3pez-Ortiz, A., van Beek, P., Golynski, A. (2004). Improved algorithms for the global cardinality constraint. In Proceedings of the 10th International Conference on Principles and Practice of Constraint Programming (CP\u201904), Lecture Notes in Computer Science. (Vol. 3258, pp. 542\u2013556). Berlin: Springer. doi: 10.1007\/978-3-540-30201-8_40 .","DOI":"10.1007\/978-3-540-30201-8_40"},{"key":"9181_CR35","unstructured":"R\u00e9gin, J.C. (1996). Generalized Arc Consistency for Global Cardinality Constraint. In Proceedings of the 13th National Conference on Artificial Intelligence (AAAI\u201996). (pp. 209\u2013215): AAAI Press . http:\/\/www.aaai.org\/Papers\/AAAI\/1996\/AAAI96-031. pdf ."},{"key":"9181_CR36","volume-title":"The handbook of constraint programming","author":"F Rossi","year":"2006","unstructured":"Rossi, F., van Beek, P., Walsh, T. (2006). The handbook of constraint programming. New York: Elsevier."},{"issue":"1","key":"9181_CR37","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s10601-009-9079-y","volume":"16","author":"M Samer","year":"2011","unstructured":"Samer, M., & Szeider, S. (2011). Tractable cases of the extended global cardinality constraint. Constraints, 16(1), 1\u201324. doi: 10.1007\/s10601-009-9079-y .","journal-title":"Constraints"},{"key":"9181_CR38","unstructured":"Schiex, T., Fargier, H., Verfaillie, G. (1995). Valued Constraint Satisfaction Problems: Hard and Easy Problems In Mellish, C (Ed.), Proceedings of the 14th International Joint Conference on Artificial Intelligence (IJCAI\u201995), (pp. 631\u2013639)."},{"key":"9181_CR39","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1007\/BF00143881","volume":"1","author":"M Wallace","year":"1996","unstructured":"Wallace, M. (1996). Practical applications of constraint programming. Constraints, 1, 139\u2013168.","journal-title":"Constraints"},{"issue":"1","key":"9181_CR40","first-page":"137","volume":"12","author":"M Wallace","year":"1997","unstructured":"Wallace, M., Novello, S., Schimpf, J. (1997). ECLiPSe: A platform for constraint logic programming. ICL Systems Journal, 12(1), 137\u2013158.","journal-title":"ICL Systems Journal"},{"key":"9181_CR41","unstructured":"Williams, R., Gomes, C.P., Selman, B. (2003). Backdoors to typical case complexity. In Proceedings of the 18th International Joint Conference on Artificial Intelligence (IJCAI\u201903). (pp. 1173\u20131178)."},{"key":"9181_CR42","unstructured":"\u017civn\u00fd, S. (2009). The complexity and expressive power of valued constraints. Doctoral dissertation: University of Oxford."}],"container-title":["Constraints"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10601-015-9181-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10601-015-9181-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10601-015-9181-2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,30]],"date-time":"2019-05-30T15:14:18Z","timestamp":1559229258000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10601-015-9181-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,2,19]]},"references-count":42,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2016,4]]}},"alternative-id":["9181"],"URL":"https:\/\/doi.org\/10.1007\/s10601-015-9181-2","relation":{},"ISSN":["1383-7133","1572-9354"],"issn-type":[{"value":"1383-7133","type":"print"},{"value":"1572-9354","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,2,19]]}}}