{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,8]],"date-time":"2024-09-08T12:29:38Z","timestamp":1725798578868},"publisher-location":"Cham","reference-count":37,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319104270"},{"type":"electronic","value":"9783319104287"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-319-10428-7_21","type":"book-chapter","created":{"date-parts":[[2014,8,13]],"date-time":"2014-08-13T01:33:54Z","timestamp":1407893634000},"page":"272-288","source":"Crossref","is-referenced-by-count":0,"title":["Subexponential Time Complexity of CSP with Global Constraints"],"prefix":"10.1007","author":[{"given":"Ronald","family":"de Haan","sequence":"first","affiliation":[]},{"given":"Iyad","family":"Kanj","sequence":"additional","affiliation":[]},{"given":"Stefan","family":"Szeider","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"21_CR1","unstructured":"Beldiceanu, N., Carlsson, M., Rampon, J.-X.: Global constraint catalog. Technical Report T2005:08, SICS, SE-16 429 Kista, Sweden (August 2006), http:\/\/www.emn.fr\/x-info\/sdemasse\/gccat\/"},{"issue":"4","key":"21_CR2","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1007\/s10601-006-9001-9","volume":"11","author":"C. Bessiere","year":"2006","unstructured":"Bessiere, C., Hebrard, E., Hnich, B., Kiziltan, Z., Walsh, T.: Filtering algorithms for the NValue constraint. Constraints\u00a011(4), 271\u2013293 (2006)","journal-title":"Constraints"},{"key":"21_CR3","unstructured":"Bessi\u00e8re, C., Hebrard, E., Hnich, B., Walsh, T.: The complexity of global constraints. In: McGuinness, D.L., Ferguson, G. (eds.) Proceedings of the Nineteenth National Conference on Artificial Intelligence, San Jose, California, USA, July 25-29, pp. 112\u2013117. AAAI Press \/ The MIT Press (2004)"},{"issue":"2","key":"21_CR4","doi-asserted-by":"publisher","first-page":"546","DOI":"10.1137\/070683933","volume":"39","author":"A. Bj\u00f6rklund","year":"2009","unstructured":"Bj\u00f6rklund, A., Husfeldt, T., Koivisto, M.: Set partitioning via inclusion-exclusion. SIAM J. Comput.\u00a039(2), 546\u2013563 (2009)","journal-title":"SIAM J. Comput."},{"key":"21_CR5","doi-asserted-by":"publisher","first-page":"194","DOI":"10.1017\/S030500410002168X","volume":"37","author":"R.L. Brooks","year":"1941","unstructured":"Brooks, R.L.: On colouring the nodes of a network. Mathematical Proceedings of the Cambridge Philosophical Society\u00a037, 194\u2013197 (1941)","journal-title":"Mathematical Proceedings of the Cambridge Philosophical Society"},{"issue":"8","key":"21_CR6","doi-asserted-by":"publisher","first-page":"847","DOI":"10.1016\/j.jcss.2010.04.003","volume":"76","author":"H. Chen","year":"2010","unstructured":"Chen, H., Grohe, M.: Constraint satisfaction with succinctly specified relations. J. of Computer and System Sciences\u00a076(8), 847\u2013860 (2010)","journal-title":"J. of Computer and System Sciences"},{"issue":"8","key":"21_CR7","doi-asserted-by":"publisher","first-page":"1346","DOI":"10.1016\/j.jcss.2006.04.007","volume":"72","author":"J. Chen","year":"2006","unstructured":"Chen, J., Huang, X., Kanj, I.A., Xia, G.: Strong computational lower bounds via parameterized complexity. J. of Computer and System Sciences\u00a072(8), 1346\u20131367 (2006)","journal-title":"J. of Computer and System Sciences"},{"issue":"6","key":"21_CR8","doi-asserted-by":"publisher","first-page":"892","DOI":"10.1016\/j.jcss.2006.11.001","volume":"73","author":"J. Chen","year":"2007","unstructured":"Chen, J., Kanj, I., Perkovic, L., Sedgwick, E., Xia, G.: Genus characterizes the complexity of certain graph problems: Some tight results. Journal of Computer and System Sciences\u00a073(6), 892\u2013907 (2007)","journal-title":"Journal of Computer and System Sciences"},{"issue":"27-29","key":"21_CR9","doi-asserted-by":"publisher","first-page":"2641","DOI":"10.1016\/j.tcs.2009.03.006","volume":"410","author":"J. Chen","year":"2009","unstructured":"Chen, J., Kanj, I.A., Xia, G.: On parameterized exponential time complexity. Theoretical Computer Science\u00a0410(27-29), 2641\u20132648 (2009)","journal-title":"Theoretical Computer Science"},{"key":"21_CR10","volume-title":"Introduction to Algorithms","author":"T.H. Cormen","year":"2009","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 3rd edn. The MIT Press, Cambridge (2009)","edition":"3"},{"key":"21_CR11","unstructured":"Dechter, R.: Constraint Processing. Morgan Kaufmann (2003)"},{"key":"21_CR12","doi-asserted-by":"publisher","first-page":"866","DOI":"10.1145\/1101821.1101823","volume":"52","author":"E. Demaine","year":"2005","unstructured":"Demaine, E., Fomin, F., Hajiaghayi, M., Thilikos, D.: Subexponential parameterized algorithms on bounded-genus graphs and H-minor-free graphs. J. ACM\u00a052, 866\u2013893 (2005)","journal-title":"J. ACM"},{"key":"21_CR13","unstructured":"Fellows, M.R., Friedrich, T., Hermelin, D., Narodytska, N., Rosamond, F.A.: Constraint satisfaction problems: Convexity makes alldifferent constraints tractable. In: Walsh, T. (ed.) IJCAI 2011, Proceedings of the 22nd International Joint Conference on Artificial Intelligence, Barcelona, Catalonia, Spain, July 16-22, pp. 522\u2013527. IJCAI\/AAAI (2011)"},{"key":"21_CR14","series-title":"Texts in Theoretical Computer Science. An EATCS Series","volume-title":"Parameterized Complexity Theory","author":"J. Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series, vol.\u00a0XIV. Springer, Berlin (2006)"},{"issue":"1","key":"21_CR15","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1145\/322290.322292","volume":"29","author":"E.C. Freuder","year":"1982","unstructured":"Freuder, E.C.: A sufficient condition for backtrack-bounded search. J. of the ACM\u00a029(1), 24\u201332 (1982)","journal-title":"J. of the ACM"},{"key":"21_CR16","unstructured":"Freuder, E.C.: Complexity of k-tree structured constraint satisfaction problems. In: Shrobe, H.E., Dietterich, T.G., Swartout, W.R. (eds.) Proceedings of the 8th National Conference on Artificial Intelligence, Boston, Massachusetts, July 29-August 3, 2 vols., pp. 4\u20139. AAAI Press \/ The MIT Press (1990)"},{"key":"21_CR17","volume-title":"Computers and Intractability","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.R.: Computers and Intractability. W. H. Freeman and Company, New York (1979)"},{"key":"21_CR18","unstructured":"Gaspers, S., Szeider, S.: Kernels for global constraints. In: Walsh, T. (ed.) Proceedings of the 22nd International Joint Conference on Artificial Intelligence, IJCAI 2011, pp. 540\u2013545. AAAI Press\/IJCAI (2011)"},{"issue":"3","key":"21_CR19","doi-asserted-by":"publisher","first-page":"579","DOI":"10.1006\/jcss.2001.1809","volume":"64","author":"G. Gottlob","year":"2002","unstructured":"Gottlob, G., Leone, N., Scarcello, F.: Hypertree decompositions and tractable queries. J. of Computer and System Sciences\u00a064(3), 579\u2013627 (2002)","journal-title":"J. of Computer and System Sciences"},{"key":"21_CR20","unstructured":"Hnich, B., Kiziltan, Z., Walsh, T.: Combining symmetry breaking with other constraints: Lexicographic ordering with sums. In: AI&M 1-2004, Eighth International Symposium on Artificial Intelligence and Mathematics, Fort Lauderdale, Florida, USA, January 4-6 (2004)"},{"issue":"2","key":"21_CR21","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1006\/jcss.2000.1727","volume":"62","author":"R. Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R.: On the complexity of k-SAT. J. of Computer and System Sciences\u00a062(2), 367\u2013375 (2001)","journal-title":"J. of Computer and System Sciences"},{"issue":"4","key":"21_CR22","doi-asserted-by":"publisher","first-page":"512","DOI":"10.1006\/jcss.2001.1774","volume":"63","author":"R. Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? J. of Computer and System Sciences\u00a063(4), 512\u2013530 (2001)","journal-title":"J. of Computer and System Sciences"},{"key":"21_CR23","doi-asserted-by":"crossref","unstructured":"Kanj, I., Szeider, S.: On the subexponential time complexity of CSP. In: Proceedings of the Twenty-Seventh AAAI Conference on Artificial Intelligence. AAAI Press (2013)","DOI":"10.1609\/aaai.v27i1.8609"},{"key":"21_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"379","DOI":"10.1007\/978-3-540-74970-7_28","volume-title":"Principles and Practice of Constraint Programming \u2013 CP 2007","author":"G. Katsirelos","year":"2007","unstructured":"Katsirelos, G., Walsh, T.: A compression algorithm for large arity extensional constraints. In: Bessi\u00e8re, C. (ed.) CP 2007. LNCS, vol.\u00a04741, pp. 379\u2013393. Springer, Heidelberg (2007)"},{"key":"#cr-split#-21_CR25.1","doi-asserted-by":"crossref","unstructured":"Kolaitis, P.G., Vardi, M.Y.: Conjunctive-query containment and constraint satisfaction. J. of Computer and System Sciences\u00a061(2), 302-332 (2000)","DOI":"10.1006\/jcss.2000.1713"},{"key":"#cr-split#-21_CR25.2","unstructured":"Special issue on the Seventeenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, Seattle, WA (1998)"},{"issue":"5","key":"21_CR26","doi-asserted-by":"publisher","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.: Simultaneous matchings: hardness and approximation. J. of Computer and System Sciences\u00a074(5), 884\u2013897 (2008)","journal-title":"J. of Computer and System Sciences"},{"key":"21_CR27","first-page":"41","volume":"105","author":"D. Lokshtanov","year":"2011","unstructured":"Lokshtanov, D., Marx, D., Saurabh, S.: Lower bounds based on the exponential time hypothesis. Bulletin of the European Association for Theoretical Computer Science\u00a0105, 41\u201372 (2011)","journal-title":"Bulletin of the European Association for Theoretical Computer Science"},{"key":"21_CR28","doi-asserted-by":"crossref","unstructured":"Marx, D.: Tractable hypergraph properties for constraint satisfaction and conjunctive queries. J. of the ACM\u00a060(6), Art. 42, 51 (2013)","DOI":"10.1145\/2535926"},{"key":"21_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1007\/978-3-540-48085-3_24","volume-title":"Principles and Practice of Constraint Programming \u2013 CP\u201999","author":"F. Pachet","year":"1999","unstructured":"Pachet, F., Roy, P.: Automatic generation of music programs. In: Jaffar, J. (ed.) CP 1999. LNCS, vol.\u00a01713, pp. 331\u2013345. Springer, Heidelberg (1999)"},{"issue":"3","key":"21_CR30","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"C.H. Papadimitriou","year":"1991","unstructured":"Papadimitriou, C.H., Yannakakis, M.: Optimization, approximation, and complexity classes. J. of Computer and System Sciences\u00a043(3), 425\u2013440 (1991)","journal-title":"J. of Computer and System Sciences"},{"key":"21_CR31","unstructured":"R\u00e9gin, J.-C.: A filtering algorithm for constraints of difference in CSPs. In: Hayes-Roth, B., Korf, R.E. (eds.) Proceedings of the 12th National Conference on Artificial Intelligence, Seattle, WA, USA, July 31-August 4, vol.\u00a01, pp. 362\u2013367. AAAI Press \/ The MIT Press (1994)"},{"key":"21_CR32","unstructured":"R\u00e9gin, J.-C.: D\u00e9veloppement d\u2019outils algorithmiques pour l\u2019Intelligence Artificielle. PhD thesis, Montpellier II (1995) (in French)"},{"key":"21_CR33","doi-asserted-by":"crossref","unstructured":"R\u00e9gin, J.-C.: Global constraints: A survey. In: van Hentenryck, P., Milano, M. (eds.) Hybrid Optimization: The Ten Years of CPAIOR. Optimization and Its Applications, vol.\u00a045, ch. 3, pp. 63\u2013134. Springer (2011)","DOI":"10.1007\/978-1-4419-1644-0_3"},{"key":"21_CR34","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"384","DOI":"10.1007\/3-540-45349-0_28","volume-title":"Principles and Practice of Constraint Programming - CP 2000","author":"J.-C. R\u00e9gin","year":"2000","unstructured":"R\u00e9gin, J.-C., Rueher, M.: A global constraint combining a sum constraint and difference constraints. In: Dechter, R. (ed.) CP 2000. LNCS, vol.\u00a01894, pp. 384\u2013395. Springer, Heidelberg (2000)"},{"issue":"2","key":"21_CR35","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1016\/j.jcss.2009.04.003","volume":"76","author":"M. Samer","year":"2010","unstructured":"Samer, M., Szeider, S.: Constraint satisfaction with bounded treewidth revisited. J. of Computer and System Sciences\u00a076(2), 103\u2013114 (2010)","journal-title":"J. of Computer and System Sciences"},{"key":"21_CR36","doi-asserted-by":"crossref","unstructured":"van Hoeve, W.-J., Katriel, I.: Global constraints. In: Rossi, F., van Beek, P., Walsh, T. (eds.) Handbook of Constraint Programming, ch. 6. Elsevier (2006)","DOI":"10.1016\/S1574-6526(06)80010-6"}],"container-title":["Lecture Notes in Computer Science","Principles and Practice of Constraint Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-10428-7_21","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,7,15]],"date-time":"2023-07-15T22:29:51Z","timestamp":1689460191000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-10428-7_21"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319104270","9783319104287"],"references-count":37,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-10428-7_21","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}