{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T06:17:10Z","timestamp":1725603430100},"publisher-location":"Berlin, Heidelberg","reference-count":27,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642237850"},{"type":"electronic","value":"9783642237867"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-23786-7_24","type":"book-chapter","created":{"date-parts":[[2011,8,31]],"date-time":"2011-08-31T03:58:42Z","timestamp":1314763122000},"page":"302-316","source":"Crossref","is-referenced-by-count":4,"title":["The Parameterized Complexity of Local Consistency"],"prefix":"10.1007","author":[{"given":"Serge","family":"Gaspers","sequence":"first","affiliation":[]},{"given":"Stefan","family":"Szeider","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"24_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1007\/978-3-540-73420-8_26","volume-title":"Automata, Languages and Programming","author":"A. Atserias","year":"2007","unstructured":"Atserias, A., Bulatov, A.A., Dalmau, V.: On the power of k-consistency. In: Arge, L., Cachin, C., Jurdzi\u0144ski, T., Tarlecki, A. (eds.) ICALP 2007. LNCS, vol.\u00a04596, pp. 279\u2013290. Springer, Heidelberg (2007)"},{"key":"24_CR2","volume-title":"Handbook of Constraint Programming","author":"C. Bessiere","year":"2006","unstructured":"Bessiere, C.: Constraint propagation. In: Rossi, F., van Beek, P., Walsh, T. (eds.) Handbook of Constraint Programming, ch. 3. Elsevier, Amsterdam (2006)"},{"issue":"4-5","key":"24_CR3","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1007\/s001530050069","volume":"36","author":"L. Cai","year":"1997","unstructured":"Cai, L., Chen, J., Downey, R.G., Fellows, M.R.: On the parameterized complexity of short computation and factorization. Archive for Mathematical Logic\u00a036(4-5), 321\u2013337 (1997)","journal-title":"Archive for Mathematical Logic"},{"key":"24_CR4","doi-asserted-by":"publisher","first-page":"654","DOI":"10.1016\/S0022-0000(03)00073-4","volume":"67","author":"M. Cesati","year":"2003","unstructured":"Cesati, M.: The Turing way to parameterized complexity. Journal of Computer and System Sciences\u00a067, 654\u2013685 (2003)","journal-title":"Journal of Computer and System Sciences"},{"key":"24_CR5","unstructured":"Cesati, M.: Compendium of parameterized problems (September 2006), http:\/\/bravo.ce.uniroma2.it\/home\/cesati\/research\/compendium.pdf"},{"key":"24_CR6","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1002\/malq.19970430204","volume":"43","author":"M. Cesati","year":"1997","unstructured":"Cesati, M., Ianni, M.D.: Computation models for parameterized complexity. Mathematical Logic Quarterly\u00a043, 179\u2013202 (1997)","journal-title":"Mathematical Logic Quarterly"},{"issue":"1","key":"24_CR7","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1016\/j.apal.2007.09.003","volume":"151","author":"Y. Chen","year":"2008","unstructured":"Chen, Y., Flum, J.: The parameterized complexity of maximality and minimality problems. Annals of Pure and Applied Logic\u00a0151(1), 22\u201361 (2008)","journal-title":"Annals of Pure and Applied Logic"},{"issue":"1","key":"24_CR8","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1016\/0004-3702(89)90080-5","volume":"41","author":"M.C. Cooper","year":"1989","unstructured":"Cooper, M.C.: An optimal k-consistency algorithm. Artificial Intelligence\u00a041(1), 89\u201395 (1989)","journal-title":"Artificial Intelligence"},{"key":"24_CR9","first-page":"295","volume-title":"IRE-AIEE-ACM 1959 (Western)","author":"R. Briandais De La","year":"1959","unstructured":"De La Briandais, R.: File searching using variable length keys. In: IRE-AIEE-ACM 1959 (Western), pp. 295\u2013298. ACM, New York (1959)"},{"issue":"1","key":"24_CR10","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1016\/0004-3702(92)90043-W","volume":"55","author":"R. Dechter","year":"1992","unstructured":"Dechter, R.: From local to global consistency. Artificial Intelligence\u00a055(1), 87\u2013107 (1992)","journal-title":"Artificial Intelligence"},{"key":"24_CR11","volume-title":"Constraint Processing","author":"R. Dechter","year":"2003","unstructured":"Dechter, R.: Constraint Processing. Morgan Kaufmann, San Francisco (2003)"},{"issue":"1","key":"24_CR12","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0004-3702(87)90002-6","volume":"34","author":"R. Dechter","year":"1987","unstructured":"Dechter, R., Pearl, J.: Network-based heuristics for constraint-satisfaction problems. Artificial Intelligence\u00a034(1), 1\u201338 (1987)","journal-title":"Artificial Intelligence"},{"key":"24_CR13","unstructured":"Downey, R.G., Fellows, M.R.: Fixed-parameter tractability and completeness. In: Proceedings of the Twenty-first Manitoba Conference on Numerical Mathematics and Computing (Winnipeg, MB, 1991), vol.\u00a087, pp. 161\u2013178 (1992)"},{"issue":"1-2","key":"24_CR14","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(1-2), 109\u2013131 (1995)","journal-title":"Theoretical Computer Science"},{"key":"24_CR15","series-title":"Monographs in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"R.G. Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Monographs in Computer Science. Springer, New York (1999)"},{"key":"24_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1007\/11847250_11","volume-title":"Parameterized and Exact Computation","author":"R.G. Downey","year":"2006","unstructured":"Downey, R.G., Fellows, M.R., McCartin, C.: Parameterized approximation problems. In: Bodlaender, H.L., Langston, M.A. (eds.) IWPEC 2006. LNCS, vol.\u00a04169, pp. 121\u2013129. Springer, Heidelberg (2006)"},{"key":"24_CR17","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)"},{"key":"24_CR18","doi-asserted-by":"publisher","first-page":"490","DOI":"10.1145\/367390.367400","volume":"3","author":"E. Fredkin","year":"1960","unstructured":"Fredkin, E.: Trie memory. Communications of the ACM\u00a03, 490\u2013499 (1960)","journal-title":"Communications of the ACM"},{"issue":"11","key":"24_CR19","doi-asserted-by":"publisher","first-page":"958","DOI":"10.1145\/359642.359654","volume":"21","author":"E.C. Freuder","year":"1978","unstructured":"Freuder, E.C.: Synthesizing constraint expressions. Communications of the ACM\u00a021(11), 958\u2013966 (1978)","journal-title":"Communications of the ACM"},{"issue":"4","key":"24_CR20","doi-asserted-by":"publisher","first-page":"755","DOI":"10.1145\/4221.4225","volume":"32","author":"E.C. Freuder","year":"1985","unstructured":"Freuder, E.C.: A sufficient condition for backtrack-bounded search. Journal of the ACM\u00a032(4), 755\u2013761 (1985)","journal-title":"Journal of the ACM"},{"issue":"6","key":"24_CR21","doi-asserted-by":"publisher","first-page":"1184","DOI":"10.1145\/504794.504798","volume":"48","author":"M. Frick","year":"2001","unstructured":"Frick, M., Grohe, M.: Deciding first-order properties of locally tree-decomposable structures. Journal of the ACM\u00a048(6), 1184\u20131206 (2001)","journal-title":"Journal of the ACM"},{"key":"24_CR22","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":"24_CR23","doi-asserted-by":"crossref","unstructured":"Gaspers, S., Szeider, S.: The parameterized complexity of local consistency. Electronic Colloquium on Computational Complexity (ECCC), Technical Report TR11-071 (2011)","DOI":"10.1007\/978-3-642-23786-7_24"},{"issue":"1","key":"24_CR24","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1016\/j.jda.2010.07.003","volume":"9","author":"C. Komusiewicz","year":"2011","unstructured":"Komusiewicz, C., Niedermeier, R., Uhlmann, J.: Deconstructing intractability - a multivariate complexity analysis of interval constrained coloring. Journal of Discrete Algorithms\u00a09(1), 137\u2013151 (2011)","journal-title":"Journal of Discrete Algorithms"},{"key":"24_CR25","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1016\/0004-3702(77)90007-8","volume":"8","author":"A.K. Mackworth","year":"1977","unstructured":"Mackworth, A.K.: Consistency in networks of relations. Artificial Intelligence\u00a08, 99\u2013118 (1977)","journal-title":"Artificial Intelligence"},{"key":"24_CR26","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1016\/0020-0255(74)90008-5","volume":"7","author":"U. Montanari","year":"1974","unstructured":"Montanari, U.: Networks of constraints: fundamental properties and applications to picture processing. Information Sciences\u00a07, 95\u2013132 (1974)","journal-title":"Information Sciences"},{"key":"24_CR27","series-title":"Oxford Lecture Series in Mathematics and its Applications","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001","volume-title":"Invitation to Fixed-Parameter Algorithms","author":"R. Niedermeier","year":"2006","unstructured":"Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford Lecture Series in Mathematics and its Applications. Oxford University Press, Oxford (2006)"}],"container-title":["Lecture Notes in Computer Science","Principles and Practice of Constraint Programming \u2013 CP 2011"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-23786-7_24","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,12,2]],"date-time":"2021-12-02T05:18:13Z","timestamp":1638422293000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-23786-7_24"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642237850","9783642237867"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-23786-7_24","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}