{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:23:12Z","timestamp":1759638192911},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2009,9,24]],"date-time":"2009-09-24T00:00:00Z","timestamp":1253750400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Constraints"],"published-print":{"date-parts":[[2011,1]]},"DOI":"10.1007\/s10601-009-9079-y","type":"journal-article","created":{"date-parts":[[2009,9,23]],"date-time":"2009-09-23T09:22:11Z","timestamp":1253697731000},"page":"1-24","source":"Crossref","is-referenced-by-count":17,"title":["Tractable cases of the extended global cardinality constraint"],"prefix":"10.1007","volume":"16","author":[{"given":"Marko","family":"Samer","sequence":"first","affiliation":[]},{"given":"Stefan","family":"Szeider","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2009,9,24]]},"reference":[{"key":"9079_CR1","unstructured":"Beldiceanu, N., Carlsson, M. & Rampon, J.-X. (2005). Global constraint catalog. Technical Report T2005:08, Swedish Institute of Computer Science, Stockholm, Sweden."},{"key":"9079_CR2","first-page":"716","volume-title":"Proceedings of the 10th international conference on principles and practice of constraint programming (CP\u201904), LNCS (Vol.\u00a03258)","author":"C Bessi\u00e9re","year":"2004","unstructured":"Bessi\u00e9re, C., Hebrard, E., Hnich, B., & Walsh, T. (2004). The tractability of global constraints. In Proceedings of the 10th international conference on principles and practice of constraint programming (CP\u201904), LNCS (Vol.\u00a03258, pp.\u00a0716\u2013720). New York: Springer."},{"key":"9079_CR3","first-page":"235","volume-title":"Proceedings of the 23rd AAAI conference on artificial intelligence\u00a0(AAAI\u201908)","author":"C Bessi\u00e9re","year":"2008","unstructured":"Bessi\u00e9re, C., Hebrard, E., Hnich, B., Kiziltan, Z., Quimper, C.-G., & Walsh, T. (2008). The parameterized complexity of global constraints. In Proceedings of the 23rd AAAI conference on artificial intelligence\u00a0(AAAI\u201908) (pp.\u00a0235\u2013240). Menlo Park: AAAI."},{"issue":"1\u20132","key":"9079_CR4","first-page":"1","volume":"11","author":"HL Bodlaender","year":"1993","unstructured":"Bodlaender, H. L. (1993). A tourist guide through treewidth. Acta Cybernetica, 11(1\u20132), 1\u201322.","journal-title":"Acta Cybernetica"},{"issue":"6","key":"9079_CR5","doi-asserted-by":"crossref","first-page":"1305","DOI":"10.1137\/S0097539793251219","volume":"25","author":"HL Bodlaender","year":"1996","unstructured":"Bodlaender, H. L. (1996). A linear time algorithm for finding tree-decompositions of small treewidth. SIAM Journal on Computing, 25(6), 1305\u20131317.","journal-title":"SIAM Journal on Computing"},{"key":"9079_CR6","first-page":"1","volume-title":"Proceedings of the 31st conference on current trends in theory and practice of computer science (SOFSEM\u201905), LNCS (Vol.\u00a03381)","author":"HL Bodlaender","year":"2005","unstructured":"Bodlaender, H. L. (2005). Discovering treewidth. In Proceedings of the 31st conference on current trends in theory and practice of computer science (SOFSEM\u201905), LNCS (Vol.\u00a03381, pp.\u00a01\u201316). New York: Springer."},{"key":"9079_CR7","first-page":"153","volume-title":"Proceedings of the 9th international conference on principles and practice of constraint programming (CP\u201903), LNCS (Vol.\u00a02833)","author":"S Bourdais","year":"2003","unstructured":"Bourdais, S., Galinier, P., & Pesant, G. (2003). HIBISCUS: A constraint programming application to staff scheduling in health care. In Proceedings of the 9th international conference on principles and practice of constraint programming (CP\u201903), LNCS (Vol.\u00a02833, pp.\u00a0153\u2013167). New York: Springer."},{"issue":"2","key":"9079_CR8","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1007\/BF00961872","volume":"4","author":"Y Caseau","year":"1995","unstructured":"Caseau, Y., Guillo, P.-Y., & Levenez, E. (1995). A deductive and object-oriented approach to a complex scheduling problem. Journal of Intelligent Information Systems, 4(2), 149\u2013166.","journal-title":"Journal of Intelligent Information Systems"},{"key":"9079_CR9","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1016\/S1574-6526(06)80012-X","volume-title":"Handbook of constraint programming (chapter\u00a08)","author":"D Cohen","year":"2006","unstructured":"Cohen, D., & Jeavons, P. (2006). The complexity of constraint languages. In F. Rossi, P. van Beek, & T. Walsh (Eds.), Handbook of constraint programming (chapter\u00a08, pp.\u00a0245\u2013280). Amsterdam: Elsevier."},{"issue":"2","key":"9079_CR10","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1016\/0095-8956(88)90068-8","volume":"45","author":"G Cornu\u00e9jols","year":"1988","unstructured":"Cornu\u00e9jols, G. (1988). General factors of graphs. Journal of Combinatorial Theory, Series B, 45(2), 185\u2013198.","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"9079_CR11","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1016\/0167-6377(82)90016-5","volume":"1","author":"G Cornu\u00e9jols","year":"1982","unstructured":"Cornu\u00e9jols, G., Hartvigsen, D., & Pulleyblank, W. (1982). Packing subgraphs in a graph. Operations Research Letters, 1, 139\u2013143.","journal-title":"Operations Research Letters"},{"key":"9079_CR12","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1016\/B978-0-444-88074-1.50010-X","volume-title":"Handbook of theoretical computer science: Formal models and semantics (Vol.\u00a0B, chapter\u00a05)","author":"B Courcelle","year":"1990","unstructured":"Courcelle, B. (1990). Graph rewriting: An algebraic and logic approach. In J. van Leeuwen (Ed.), Handbook of theoretical computer science: Formal models and semantics (Vol.\u00a0B, chapter\u00a05, pp.\u00a0193\u2013242). Amsterdam: Elsevier."},{"key":"9079_CR13","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1016\/S1574-6526(06)80011-8","volume-title":"Handbook of constraint programming (chapter\u00a07)","author":"R Dechter","year":"2006","unstructured":"Dechter, R. (2006). Tractable structures for constraint satisfaction problems. In F. Rossi, P. van Beek, & T. Walsh (Eds.), Handbook of constraint programming (chapter\u00a07, pp.\u00a0209\u2013244). Amsterdam: Elsevier."},{"key":"9079_CR14","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized complexity","author":"RG Downey","year":"1999","unstructured":"Downey, R. G., & Fellows, M. R. (1999). Parameterized complexity. New York: Springer."},{"key":"9079_CR15","volume-title":"Parameterized complexity theory","author":"J Flum","year":"2006","unstructured":"Flum, J., & Grohe, M. (2006). Parameterized complexity theory. New York: Springer."},{"key":"9079_CR16","first-page":"250","volume-title":"Proceedings of the 21st AAAI conference on artificial intelligence (AAAI\u201906)","author":"G Gottlob","year":"2006","unstructured":"Gottlob, G., & Pichler, R., & Wei, F. (2006). Bounded treewidth as a key to tractability of knowledge representation and reasoning. In Proceedings of the 21st AAAI conference on artificial intelligence (AAAI\u201906) (pp.\u00a0250\u2013256). Menlo Park: AAAI."},{"key":"9079_CR17","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1016\/S1574-6526(06)80010-6","volume-title":"Handbook of constraint programming (chapter\u00a06)","author":"W-J Hoeve van","year":"2006","unstructured":"van Hoeve, W.-J., & Katriel I. (2006). Global constraints. In F. Rossi, P. van Beek, & T. Walsh (Eds.), Handbook of constraint programming (chapter\u00a06, pp.\u00a0169\u2013208). Amsterdam: Elsevier."},{"key":"9079_CR18","doi-asserted-by":"crossref","DOI":"10.1007\/BFb0045375","volume-title":"Treewidth: Computations and approximations","author":"T Kloks","year":"1994","unstructured":"Kloks, T. (1994). Treewidth: Computations and approximations. New York: Springer."},{"key":"9079_CR19","doi-asserted-by":"crossref","first-page":"54","DOI":"10.1016\/S1571-0653(05)80078-2","volume":"8","author":"AMCA Koster","year":"2001","unstructured":"Koster, A. M. C. A., Bodlaender, H. L., & van Hoesel, S. P. M. (2001). Treewidth: Computational experiments. Electronic Notes in Discrete Mathematics, 8, 54\u201357.","journal-title":"Electronic Notes in Discrete Mathematics"},{"key":"9079_CR20","first-page":"243","volume-title":"Combinatorial structures and their applications","author":"L Lov\u00e1sz","year":"1970","unstructured":"Lov\u00e1sz, L. (1970). The factorization of graphs. In Combinatorial structures and their applications (pp.\u00a0243\u2013246). New York: Gordon and Breach."},{"key":"9079_CR21","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1007\/BF01889919","volume":"23","author":"L Lov\u00e1sz","year":"1972","unstructured":"Lov\u00e1sz, L. (1972). The factorization of graphs\u00a0II. Acta Mathematica Academiae Scientiarum Hungaricae, 23, 223\u2013246.","journal-title":"Acta Mathematica Academiae Scientiarum Hungaricae"},{"key":"9079_CR22","doi-asserted-by":"crossref","unstructured":"Micali, S., & Vazirani, V. V. (1980). An ${O}(\\sqrt{|{V}|}\\cdot |{E}|)$ algorithm for finding a maximum matching in general graphs. In Proceedings of the 21st annual IEEE symposium on foundations of computer science (SFCS\u201980) (pp.\u00a017\u201327). IEEE Computer Society.","DOI":"10.1109\/SFCS.1980.12"},{"key":"9079_CR23","doi-asserted-by":"crossref","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001","volume-title":"Invitation to fixed-parameter algorithms","author":"R Niedermeier","year":"2006","unstructured":"Niedermeier, R. (2006). Invitation to fixed-parameter algorithms. Oxford: Oxford University Press."},{"issue":"4","key":"9079_CR24","doi-asserted-by":"crossref","first-page":"757","DOI":"10.1016\/S0022-0000(03)00078-3","volume":"67","author":"K Pietrzak","year":"2003","unstructured":"Pietrzak, K. (2003). On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems. Journal of Computer and System Sciences, 67(4), 757\u2013771.","journal-title":"Journal of Computer and System Sciences"},{"key":"9079_CR25","first-page":"542","volume-title":"Proceedings of the 10th international conference on principles and practice of constraint programming (CP\u201904), LNCS(Vol.\u00a03258)","author":"C-G Quimper","year":"2004","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), LNCS (Vol.\u00a03258, pp.\u00a0542\u2013556). New York: Springer."},{"key":"9079_CR26","first-page":"209","volume-title":"Proceedings of the 13th AAAI conference on artificial intelligence (AAAI\u201996)","author":"J-C R\u00e9gin","year":"1996","unstructured":"R\u00e9gin, J.-C. (1996). Generalized arc consistency for global cardinality constraint. In Proceedings of the 13th AAAI conference on artificial intelligence (AAAI\u201996) (pp.\u00a0209\u2013215). Menlo Park: AAAI."},{"key":"9079_CR27","first-page":"572","volume-title":"Proceedings of the 10th international conference on principles and practice of constraint programming (CP\u201904), LNCS (Vol.\u00a03258)","author":"J-C R\u00e9gin","year":"2004","unstructured":"R\u00e9gin, J.-C., & Gomes, C. P. (2004). The cardinality matrix constraint. In Proceedings of the 10th international conference on principles and practice of constraint programming (CP\u201904), LNCS (Vol.\u00a03258, pp.\u00a0572\u2013587). New York: Springer.","edition":"3258"},{"key":"9079_CR28","volume-title":"Handbook of constraint programming","year":"2006","unstructured":"Rossi, F., van Beek, P., & Walsh, T. (Eds.) (2006). Handbook of constraint programming. Amsterdam: Elsevier."},{"key":"9079_CR29","first-page":"67","volume-title":"Proceedings of the 14th computing: The Australasian theory symposium (CATS\u201908), Theory of Computing 2008, CRPIT (Vol.\u00a077)","author":"M Samer","year":"2008","unstructured":"Samer, M., & Szeider, S. (2008). Tractable cases of the extended global cardinality constraint. In Proceedings of the 14th computing: The Australasian theory symposium (CATS\u201908), Theory of Computing 2008, CRPIT (Vol.\u00a077, pp.\u00a067\u201374). Canberra: Australian Computer Society.","edition":"77"},{"issue":"2","key":"9079_CR30","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1007\/s10601-006-9006-4","volume":"12","author":"M Sellmann","year":"2007","unstructured":"Sellmann, M., Gellermann, T., & Wright, R. (2007). Cost-based filtering for shorter path constraints. Constraints, 12(2), 207\u2013238.","journal-title":"Constraints"}],"container-title":["Constraints"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10601-009-9079-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10601-009-9079-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10601-009-9079-y","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,30]],"date-time":"2019-05-30T19:14:15Z","timestamp":1559243655000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10601-009-9079-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,9,24]]},"references-count":30,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2011,1]]}},"alternative-id":["9079"],"URL":"https:\/\/doi.org\/10.1007\/s10601-009-9079-y","relation":{},"ISSN":["1383-7133","1572-9354"],"issn-type":[{"value":"1383-7133","type":"print"},{"value":"1572-9354","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,9,24]]}}}