{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:34:48Z","timestamp":1759638888391},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642296994"},{"type":"electronic","value":"9783642297007"}],"license":[{"start":{"date-parts":[[2012,1,1]],"date-time":"2012-01-01T00:00:00Z","timestamp":1325376000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-29700-7_19","type":"book-chapter","created":{"date-parts":[[2012,4,28]],"date-time":"2012-04-28T08:25:56Z","timestamp":1335601556000},"page":"199-211","source":"Crossref","is-referenced-by-count":7,"title":["Kernels for Packing and Covering Problems"],"prefix":"10.1007","author":[{"given":"Jianer","family":"Chen","sequence":"first","affiliation":[]},{"given":"Henning","family":"Fernau","sequence":"additional","affiliation":[]},{"given":"Peter","family":"Shaw","sequence":"additional","affiliation":[]},{"given":"Jianxin","family":"Wang","sequence":"additional","affiliation":[]},{"given":"Zhibiao","family":"Yang","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"19_CR1","doi-asserted-by":"publisher","first-page":"621","DOI":"10.1016\/j.ipl.2010.04.020","volume":"110","author":"F.N. Abu-Khzam","year":"2010","unstructured":"Abu-Khzam, F.N.: An improved kernelization algorithm for r-Set Packing. IPL\u00a0110, 621\u2013624 (2010)","journal-title":"IPL"},{"issue":"7","key":"19_CR2","first-page":"524","volume":"76","author":"F.N. Abu-Khzam","year":"2010","unstructured":"Abu-Khzam, F.N.: A kernelization algorithm for d-Hitting Set. JCSS\u00a076(7), 524\u2013531 (2010)","journal-title":"JCSS"},{"key":"19_CR3","first-page":"423","volume":"75","author":"H.L. Bodlaender","year":"2009","unstructured":"Bodlaender, H.L., Downey, R.G., Fellows, M.R., Hermelin, D.: On problems without polynomial kernels. JCSS\u00a075, 423\u2013434 (2009)","journal-title":"JCSS"},{"key":"19_CR4","doi-asserted-by":"crossref","unstructured":"Bodlaender, H.L., Fomin, F.V., Lokshtanov, D., Penninkx, E., Saurabh, S., Thilikos, D.M.: (Meta) kernelization. In: FOCS, pp. 629\u2013638. IEEE Computer Society (2009)","DOI":"10.1109\/FOCS.2009.46"},{"key":"19_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"635","DOI":"10.1007\/978-3-642-04128-0_57","volume-title":"Algorithms - ESA 2009","author":"H.L. Bodlaender","year":"2009","unstructured":"Bodlaender, H.L., Thomass\u00e9, S., Yeo, A.: Kernel Bounds for Disjoint Cycles and Disjoint Paths. In: Fiat, A., Sanders, P. (eds.) ESA 2009. LNCS, vol.\u00a05757, pp. 635\u2013646. Springer, Heidelberg (2009)"},{"key":"19_CR6","doi-asserted-by":"publisher","first-page":"1077","DOI":"10.1137\/050646354","volume":"37","author":"J. Chen","year":"2007","unstructured":"Chen, J., Fernau, H., Kanj, Y.A., Xia, G.: Parametric duality and kernelization: lower bounds and upper bounds on kernel size. SIAM J. Comput.\u00a037, 1077\u20131108 (2007)","journal-title":"SIAM J. Comput."},{"key":"19_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","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., Fellows, M., Juedes, D.W.: Linear Kernels in Linear Time, or How to Save k Colors in O(n\n                2) Steps. In: Hromkovi\u010d, J., Nagl, M., Westfechtel, B. (eds.) WG 2004. LNCS, vol.\u00a03353, pp. 257\u2013269. Springer, Heidelberg (2004)"},{"key":"19_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1007\/978-3-540-28639-4_24","volume-title":"Parameterized and Exact Computation","author":"F. Dehne","year":"2004","unstructured":"Dehne, F., Fellows, M., Rosamond, F.A., Shaw, P.: Greedy Localization, Iterative Compression, and 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":"19_CR9","doi-asserted-by":"crossref","unstructured":"Dell, H., van Melkebeek, D.: Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses. In: STOC, pp. 251\u2013260. ACM (2010)","DOI":"10.1145\/1806689.1806725"},{"key":"19_CR10","doi-asserted-by":"crossref","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer (1999)","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"19_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-540-39890-5_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":"19_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"34","DOI":"10.1007\/978-3-642-14031-0_6","volume-title":"Computing and Combinatorics","author":"H. Fernau","year":"2010","unstructured":"Fernau, H., Fomin, F.V., Philip, G., Saurabh, S.: The Curse of Connectivity: t-Total Vertex (Edge) Cover. In: Thai, M.T., Sahni, S. (eds.) COCOON 2010. LNCS, vol.\u00a06196, pp. 34\u201343. Springer, Heidelberg (2010)"},{"key":"19_CR13","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1007\/s10878-009-9230-0","volume":"18","author":"H. Fernau","year":"2009","unstructured":"Fernau, H., Raible, D.: A parameterized perspective on packing paths of length two. J. Comb. Optim.\u00a018, 319\u2013341 (2009)","journal-title":"J. Comb. Optim."},{"key":"19_CR14","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Text in Theoretical Computer Science. Springer (2006)"},{"key":"19_CR15","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Lokshtanov, D., Saurabh, S., Thilikos, D.M.: Bidimensionality and kernels. In: SODA, pp. 503\u2013510. SIAM (2010)","DOI":"10.1137\/1.9781611973075.43"},{"key":"19_CR16","doi-asserted-by":"crossref","unstructured":"Fortnow, L., Santhanam, R.: Infeasibility of instance compression and succinct PCPs for NP. In: STOC, pp. 133\u2013142. ACM (2008)","DOI":"10.1145\/1374376.1374398"},{"key":"19_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1007\/978-3-540-73420-8_34","volume-title":"Automata, Languages and Programming","author":"J. Guo","year":"2007","unstructured":"Guo, J., Niedermeier, R.: Linear Problem Kernels for NP-Hard Problems on Planar Graphs. In: Arge, L., Cachin, C., Jurdzi\u0144ski, T., Tarlecki, A. (eds.) ICALP 2007. LNCS, vol.\u00a04596, pp. 375\u2013386. Springer, Heidelberg (2007)"},{"key":"19_CR18","unstructured":"Kratsch, S.: Polynomial kernelizations for MIN F\n                \u2009+\u2009\u03a01 and MAX NP. In: STACS. Leibniz International Proceedings in Informatics (LIPIcs), vol.\u00a03, pp. 601\u2013612. Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik (2009)"},{"key":"19_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"489","DOI":"10.1007\/978-3-642-15155-2_43","volume-title":"Mathematical Foundations of Computer Science 2010","author":"S. Kratsch","year":"2010","unstructured":"Kratsch, S., Marx, D., Wahlstr\u00f6m, M.: Parameterized Complexity and Kernelizability of Max Ones and Exact Ones Problems. In: Hlin\u011bn\u00fd, P., Ku\u010dera, A. (eds.) MFCS 2010. LNCS, vol.\u00a06281, pp. 489\u2013500. Springer, Heidelberg (2010)"},{"key":"19_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"264","DOI":"10.1007\/978-3-642-11269-0_22","volume-title":"Parameterized and Exact Computation","author":"S. Kratsch","year":"2009","unstructured":"Kratsch, S., Wahlstr\u00f6m, M.: Two Edge Modification Problems without Polynomial Kernels. In: Chen, J., Fomin, F.V. (eds.) IWPEC 2009. LNCS, vol.\u00a05917, pp. 264\u2013275. Springer, Heidelberg (2009)"},{"key":"19_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"401","DOI":"10.1007\/978-3-540-95891-8_37","volume-title":"SOFSEM 2009: Theory and Practice of Computer Science","author":"H. Moser","year":"2009","unstructured":"Moser, H.: A Problem Kernelization for Graph Packing. In: Nielsen, M., Ku\u010dera, A., Miltersen, P.B., Palamidessi, C., T\u016fma, P., Valencia, F. (eds.) SOFSEM 2009. LNCS, vol.\u00a05404, pp. 401\u2013412. Springer, Heidelberg (2009)"},{"key":"19_CR22","doi-asserted-by":"crossref","unstructured":"Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford University Press (2006)","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001"},{"key":"19_CR23","unstructured":"Prieto, E.: Systematic Kernelization in FPT Algorithm Design. PhD thesis, The University of Newcastle, Australia (2005)"},{"key":"19_CR24","doi-asserted-by":"publisher","first-page":"437","DOI":"10.1016\/j.tcs.2005.10.009","volume":"351","author":"E. Prieto","year":"2006","unstructured":"Prieto, E., Sloper, C.: Looking at the stars. TCS\u00a0351, 437\u2013445 (2006)","journal-title":"TCS"},{"key":"19_CR25","doi-asserted-by":"publisher","first-page":"188","DOI":"10.1016\/j.ipl.2009.12.002","volume":"110","author":"J. Wang","year":"2010","unstructured":"Wang, J., Ning, D., Feng, Q., Chen, J.: An improved kernelization for P\n                2-packing. IPL\u00a0110, 188\u2013192 (2010)","journal-title":"IPL"}],"container-title":["Lecture Notes in Computer Science","Frontiers in Algorithmics and Algorithmic Aspects in Information and Management"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-29700-7_19","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,9]],"date-time":"2020-01-09T03:50:39Z","timestamp":1578541839000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-29700-7_19"}},"subtitle":["(Extended Abstract)"],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642296994","9783642297007"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-29700-7_19","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}