{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,15]],"date-time":"2024-09-15T14:12:52Z","timestamp":1726409572994},"publisher-location":"Berlin, Heidelberg","reference-count":28,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540725039"},{"type":"electronic","value":"9783540725046"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-72504-6_64","type":"book-chapter","created":{"date-parts":[[2007,7,22]],"date-time":"2007-07-22T11:36:39Z","timestamp":1185104199000},"page":"703-714","source":"Crossref","is-referenced-by-count":0,"title":["Kernelizations for Parameterized Counting Problems"],"prefix":"10.1007","author":[{"given":"Marc","family":"Thurley","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"64_CR1","series-title":"Lecture Notes in Computer Science","volume-title":"Algorithms \u2013 ESA 2004","year":"2004","unstructured":"Albers, S., Radzik, T. (eds.): ESA 2004. LNCS, vol.\u00a03221. Springer, Heidelberg (2004)"},{"issue":"2","key":"64_CR2","doi-asserted-by":"publisher","first-page":"308","DOI":"10.1016\/0196-6774(91)90006-K","volume":"12","author":"S. Arnborg","year":"1991","unstructured":"Arnborg, S., Lagergren, J., Seese, D.: Easy problems for tree-decomposable graphs. J. Algorithms\u00a012(2), 308\u2013340 (1991)","journal-title":"J. Algorithms"},{"key":"64_CR3","series-title":"Lecture Notes in Computer Science","volume-title":"Graph-Theoretic Concepts in Computer Science","year":"2003","unstructured":"Bodlaender, H.L. (ed.): WG 2003. LNCS, vol.\u00a02880. Springer, Heidelberg (2003)"},{"key":"64_CR4","series-title":"Texts in Algorithmics","volume-title":"Algorithms and Complexity in Durham 2005 - Proceedings of the First ACiD Workshop","year":"2005","unstructured":"Broersma, H., Johnson, M., Szeider, S. (eds.): Algorithms and Complexity in Durham 2005 - Proceedings of the First ACiD Workshop, Durham, UK, 8-10 July 2005. Texts in Algorithmics, vol.\u00a04. King\u2019s College Publications, London (2005)"},{"issue":"2","key":"64_CR5","doi-asserted-by":"publisher","first-page":"280","DOI":"10.1006\/jagm.2001.1186","volume":"41","author":"J. Chen","year":"2001","unstructured":"Chen, J., Kanj, I.A., Jia, W.: Vertex cover: Further observations and further improvements. J. Algorithms\u00a041(2), 280\u2013301 (2001)","journal-title":"J. Algorithms"},{"key":"64_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1007\/978-3-540-30559-0_22","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"B. Chor","year":"2004","unstructured":"Chor, B., Juedes, D.W., Fellows, M.: Linear kernels in linear time, or how to save k colors in o(n\n                    \n                      \n                    \n                    $^{\\mbox{2}}$\n                  ) steps. In: Hromkovi\u010d, J., Nagl, M., Westfechtel, B. (eds.) WG 2004. LNCS, vol.\u00a03353, pp. 257\u2013269. Springer, Heidelberg (2004)"},{"issue":"1-2","key":"64_CR7","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1016\/S0166-218X(00)00221-3","volume":"108","author":"B. Courcelle","year":"2001","unstructured":"Courcelle, B., Makowsky, J.A., Rotics, U.: On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic. Discrete Applied Mathematics\u00a0108(1-2), 23\u201352 (2001)","journal-title":"Discrete Applied Mathematics"},{"key":"64_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"271","DOI":"10.1007\/978-3-540-28639-4_24","volume-title":"Parameterized and Exact Computation","author":"F.K.H.A. Dehne","year":"2004","unstructured":"Dehne, F.K.H.A., et al.: Greedy localization, iterative compression, modeled crown reductions: New fpt techniques, an improved algorithm for set splitting, and a novel 2k kernelization for vertex cover. In: Downey, R.G., Fellows, M.R., Dehne, F. (eds.) IWPEC 2004. LNCS, vol.\u00a03162, pp. 271\u2013280. Springer, Heidelberg (2004)"},{"key":"64_CR9","series-title":"Lecture Notes in Computer Science","volume-title":"Algorithms and Data Structures","year":"2005","unstructured":"Dehne, F., L\u00f3pez-Ortiz, A., Sack, J.-R. (eds.): WADS 2005. LNCS, vol.\u00a03608. Springer, Heidelberg (2005)"},{"key":"64_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1007\/978-3-540-30140-0_26","volume-title":"Algorithms \u2013 ESA 2004","author":"J. D\u00edaz","year":"2004","unstructured":"D\u00edaz, J., Serna, M.J., Thilikos, D.M.: Fixed parameter algorithms for counting and deciding bounded restrictive list h-colorings. In: Albers, S., Radzik, T. (eds.) ESA 2004. LNCS, vol.\u00a03221, pp. 275\u2013286. Springer, Heidelberg (2004)"},{"key":"64_CR11","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1007\/978-1-4612-2566-9_7","volume-title":"Feasible Mathematics II","author":"R.G. Downey","year":"1995","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized computational feasibility. In: Clote, P., Remmel, J. (eds.) Feasible Mathematics II, pp. 219\u2013244. Birkh\u00e4user, Boston (1995)"},{"key":"64_CR12","unstructured":"Downey, R.G., Fellows, M.R.: Fixed parameter tractability and completeness. In: Complexity Theory: Current Research, pp. 191\u2013225 (1992)"},{"key":"64_CR13","doi-asserted-by":"crossref","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. Springer, Heidelberg (1999)"},{"key":"64_CR14","series-title":"Lecture Notes in Computer Science","volume-title":"Parameterized and Exact Computation","year":"2004","unstructured":"Downey, R.G., Fellows, M.R., Dehne, F. (eds.): IWPEC 2004. LNCS, vol.\u00a03162. Springer, Heidelberg (2004)"},{"key":"64_CR15","series-title":"Lecture Notes in Computer Science","first-page":"1","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"M.R. Fellows","year":"2003","unstructured":"Fellows, M.R.: Blow-ups, win\/win\u2019s, and crown rules: Some new directions in fpt. In: Bodlaender, H.L. (ed.) WG 2003. LNCS, vol.\u00a02880, pp. 1\u201312. Springer, Heidelberg (2003)"},{"key":"64_CR16","unstructured":"Fernau, H.: Parameterized algorithmics: A graph-theoretic approach. Habilitationsschrift, Universit\u00e4t T\u00fcbingen (2005)"},{"key":"64_CR17","volume-title":"Parameterized Complexity Theory","author":"J. Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Heidelberg (2006)"},{"key":"64_CR18","unstructured":"Frick, M.: Easy Instances for Model Checking. PhD thesis, Universit\u00e4t Freiburg (2001)"},{"key":"64_CR19","series-title":"Texts in Algorithmics","first-page":"105","volume-title":"Algorithms and Complexity in Durham 2005 - Proceedings of the First ACiD Workshop","author":"D. Lokshtanov","year":"2005","unstructured":"Lokshtanov, D., Sloper, C.: Fixed parameter set splitting, linear kernel and improved running time. In: Broersma, H., Johnson, M., Szeider, S. (eds.) Algorithms and Complexity in Durham 2005 - Proceedings of the First ACiD Workshop, Durham, UK, 8-10 July 2005. Texts in Algorithmics, vol.\u00a04, pp. 105\u2013113. King\u2019s College Publications, London (2005)"},{"key":"64_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1007\/978-3-540-28639-4_12","volume-title":"Parameterized and Exact Computation","author":"L. Mathieson","year":"2004","unstructured":"Mathieson, L., Prieto, E., Shaw, P.: Packing edge disjoint triangles: A parameterized view. In: Downey, R.G., Fellows, M.R., Dehne, F. (eds.) IWPEC 2004. LNCS, vol.\u00a03162, pp. 127\u2013137. Springer, Heidelberg (2004)"},{"key":"64_CR21","unstructured":"Niedermeier, R.: Invitation to fixed-parameter algorithms. Habilitationsschrift, Universit\u00e4t T\u00fcbingen (2002)"},{"key":"64_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1007\/11534273_10","volume-title":"Algorithms and Data Structures","author":"N. Nishimura","year":"2005","unstructured":"Nishimura, N., Ragde, P., Thilikos, D.M.: Parameterized counting algorithms for general graph covering problems. In: Dehne, F., L\u00f3pez-Ortiz, A., Sack, J.-R. (eds.) WADS 2005. LNCS, vol.\u00a03608, pp. 99\u2013109. Springer, Heidelberg (2005)"},{"key":"64_CR23","volume-title":"Computational Complexity","author":"C.H. Papadimitriou","year":"1994","unstructured":"Papadimitriou, C.H.: Computational Complexity. Pearson, London (1994)"},{"key":"64_CR24","unstructured":"Rossmanith, P. (unpublished)"},{"issue":"1-2","key":"64_CR25","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1016\/0004-3702(94)00092-1","volume":"82","author":"D. Roth","year":"1996","unstructured":"Roth, D.: On the hardness of approximate reasoning. Artif. Intell.\u00a082(1-2), 273\u2013302 (1996)","journal-title":"Artif. Intell."},{"key":"64_CR26","unstructured":"Thurley, M.: Tractability and intractability of parameterized counting problems. Diploma thesis. Humboldt Universit\u00e4t zu Berlin (2006)"},{"key":"64_CR27","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/0304-3975(79)90044-6","volume":"8","author":"L.G. Valiant","year":"1979","unstructured":"Valiant, L.G.: The complexity of computing the permanent. Theor. Comput. Sci.\u00a08, 189\u2013201 (1979)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"64_CR28","doi-asserted-by":"publisher","first-page":"410","DOI":"10.1137\/0208032","volume":"8","author":"L.G. Valiant","year":"1979","unstructured":"Valiant, L.G.: The complexity of enumeration and reliability problems. SIAM J. Comput.\u00a08(3), 410\u2013421 (1979)","journal-title":"SIAM J. Comput."}],"container-title":["Lecture Notes in Computer Science","Theory and Applications of Models of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-72504-6_64.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T09:38:29Z","timestamp":1619516309000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-72504-6_64"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540725039","9783540725046"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-72504-6_64","relation":{},"subject":[]}}