{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T03:13:31Z","timestamp":1761621211838,"version":"3.41.0"},"publisher-location":"Cham","reference-count":19,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319171418"},{"type":"electronic","value":"9783319171425"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-17142-5_35","type":"book-chapter","created":{"date-parts":[[2015,4,15]],"date-time":"2015-04-15T11:19:29Z","timestamp":1429096769000},"page":"415-427","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Kernelization Algorithms for Packing Problems Allowing Overlaps"],"prefix":"10.1007","author":[{"given":"Henning","family":"Fernau","sequence":"first","affiliation":[]},{"given":"Alejandro","family":"L\u00f3pez-Ortiz","sequence":"additional","affiliation":[]},{"given":"Jazm\u00edn","family":"Romero","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,4,16]]},"reference":[{"issue":"16","key":"35_CR1","doi-asserted-by":"publisher","first-page":"621","DOI":"10.1016\/j.ipl.2010.04.020","volume":"110","author":"FN Abu-Khzam","year":"2010","unstructured":"Abu-Khzam, F.N.: An improved kernelization algorithm for $$r$$-set packing. Inf. Process. Lett. 110(16), 621\u2013624 (2010)","journal-title":"Inf. Process. Lett."},{"key":"35_CR2","doi-asserted-by":"crossref","unstructured":"Banerjee, S., Khuller, S.: A clustering scheme for hierarchical control in multi-hop wireless networks. In: Proceedings of 20th Joint Conference of the IEEE Computer and Communications Societies (INFOCOM 2001), vol. 2, pp. 1028\u20131037. IEEE Society Press (2001)","DOI":"10.1109\/INFCOM.2001.916296"},{"key":"35_CR3","unstructured":"Bodlaender, H.L., Thomass\u00e9, S., Yeo, A.: Analysis of data reduction: transformations give evidence for non-existence of polynomial kernels. Technical report. UU-CS-2008-030, Department of Information and Computer Sciences, Utrecht University (2008)"},{"key":"35_CR4","doi-asserted-by":"crossref","unstructured":"Dell, H., Marx, D.: Kernelization of packing problems. In: Rabani, Y. (ed.) Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA. pp. 68\u201381. SIAM (2012)","DOI":"10.1137\/1.9781611973099.6"},{"issue":"1","key":"35_CR5","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1016\/j.disopt.2010.09.006","volume":"8","author":"M Fellows","year":"2011","unstructured":"Fellows, M., Guo, J., Komusiewicz, C., Niedermeier, R., Uhlmann, J.: Graph-based data clustering with overlaps. Discrete Optim. 8(1), 2\u201317 (2011)","journal-title":"Discrete Optim."},{"issue":"2","key":"35_CR6","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1007\/s00453-007-9146-y","volume":"52","author":"M Fellows","year":"2008","unstructured":"Fellows, M., Knauer, C., Nishimura, N., Ragde, P., Rosamond, F., Stege, U., Thilikos, D., Whitesides, S.: Faster fixed-parameter tractable algorithms for matching and packing problems. Algorithmica 52(2), 167\u2013176 (2008)","journal-title":"Algorithmica"},{"key":"35_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1007\/978-3-540-30559-0_20","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"M Fellows","year":"2004","unstructured":"Fellows, M., Heggernes, P., Rosamond, F.A., Sloper, C., Telle, J.A.: Finding k disjoint triangles in an arbitrary graph. In: Hromkovi\u010d, J., Nagl, M., Westfechtel, B. (eds.) WG 2004. LNCS, vol. 3353, pp. 235\u2013244. Springer, Heidelberg (2004)"},{"key":"35_CR8","doi-asserted-by":"crossref","unstructured":"Fernau, H., L\u00f3pez-Ortiz, A., Romero, J.: Kernelization algorithms for packing problems allowing overlaps (Extended Version) (2014). arXiv:1411.6915","DOI":"10.1007\/978-3-319-17142-5_35"},{"issue":"4","key":"35_CR9","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. 18(4), 319\u2013341 (2009)","journal-title":"J. Comb. Optim."},{"key":"35_CR10","doi-asserted-by":"crossref","unstructured":"Giannopoulou, A.C., Jansen, B.M.P., Lokshtanov, D., Saurabh, S.: Uniform kernelization complexity of hitting forbidding minors (2014, unpublished). http:\/\/www.win.tue.nl\/~bjansen\/publications.html","DOI":"10.1007\/978-3-662-47672-7_51"},{"key":"35_CR11","doi-asserted-by":"crossref","unstructured":"Jansen, B.M.P., Marx, D.: Characterizing the easy-to-find subgraphs from the viewpoint of polynomial-time algorithms, kernels, and Turing kernels. CoRR abs\/1410.0855 (2014)","DOI":"10.1137\/1.9781611973730.42"},{"key":"35_CR12","doi-asserted-by":"crossref","unstructured":"Kirkpatrick, D., Hell, P.: On the completeness of a generalized matching problem. In: Proceedings of the Tenth Annual ACM Symposium on Theory of Computing (STOC), pp. 240\u2013245 (1978)","DOI":"10.1145\/800133.804353"},{"key":"35_CR13","doi-asserted-by":"crossref","unstructured":"Micali, S., Vazirani, V.V.: An $$O(\\sqrt{|V|}|E|)$$ algorithm for finding maximum matching in general graphs. In: Proceedings of the 21st Annual Symposium on Foundations of Computer Science, SFCS 1980, pp. 17\u201327. IEEE Computer Society (1980)","DOI":"10.1109\/SFCS.1980.12"},{"key":"35_CR14","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. 5404, pp. 401\u2013412. Springer, Heidelberg (2009)"},{"issue":"7043","key":"35_CR15","doi-asserted-by":"publisher","first-page":"814","DOI":"10.1038\/nature03607","volume":"435","author":"G Palla","year":"2005","unstructured":"Palla, G., Der\u00e9nyi, I., Farkas, I., Vicsek, T.: Uncovering the overlapping community structure of complex networks in nature and society. Nature 435(7043), 814\u2013818 (2005)","journal-title":"Nature"},{"issue":"3","key":"35_CR16","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. Theoret. Comput. Sci. 351(3), 437\u2013445 (2006)","journal-title":"Theoret. Comput. Sci."},{"key":"35_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1007\/978-3-319-04657-0_13","volume-title":"Algorithms and Computation","author":"J Romero","year":"2014","unstructured":"Romero, J., L\u00f3pez-Ortiz, A.: The $${\\cal G}$$-packing with t-overlap problem. In: Pal, S.P., Sadakane, K. (eds.) WALCOM 2014. LNCS, vol. 8344, pp. 114\u2013124. Springer, Heidelberg (2014)"},{"key":"35_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1007\/978-3-319-06686-8_25","volume-title":"Computer Science - Theory and Applications","author":"J Romero","year":"2014","unstructured":"Romero, J., L\u00f3pez-Ortiz, A.: A parameterized algorithm for packing overlapping subgraphs. In: Hirsch, E.A., Kuznetsov, S.O., Pin, J.\u00c9., Vereshchagin, N.K. (eds.) CSR 2014. LNCS, vol. 8476, pp. 325\u2013336. Springer, Heidelberg (2014)"},{"issue":"2","key":"35_CR19","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1016\/0020-0190(81)90009-0","volume":"12","author":"Y Shiloach","year":"1981","unstructured":"Shiloach, Y.: Another look at the degree constrained subgraph problem. Inf. Process. Lett. 12(2), 89\u201392 (1981)","journal-title":"Inf. Process. Lett."}],"container-title":["Lecture Notes in Computer Science","Theory and Applications of Models of Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-17142-5_35","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,22]],"date-time":"2025-05-22T15:34:28Z","timestamp":1747928068000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-17142-5_35"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319171418","9783319171425"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-17142-5_35","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"16 April 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}