{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,7]],"date-time":"2025-08-07T08:58:09Z","timestamp":1754557089000},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642137303"},{"type":"electronic","value":"9783642137310"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-13731-0_30","type":"book-chapter","created":{"date-parts":[[2010,6,10]],"date-time":"2010-06-10T11:00:50Z","timestamp":1276167650000},"page":"310-321","source":"Crossref","is-referenced-by-count":4,"title":["Polynomial Kernels for Hard Problems on Disk Graphs"],"prefix":"10.1007","author":[{"given":"Bart","family":"Jansen","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"30_CR1","series-title":"Monographs in Computer Science","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized complexity","author":"R. Downey","year":"1999","unstructured":"Downey, R., Fellows, M.R.: Parameterized complexity. Monographs in Computer Science. Springer, New York (1999)"},{"key":"30_CR2","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1145\/1233481.1233493","volume":"38","author":"J. Guo","year":"2007","unstructured":"Guo, J., Niedermeier, R.: Invitation to data reduction and problem kernelization. SIGACT News\u00a038, 31\u201345 (2007)","journal-title":"SIGACT News"},{"key":"30_CR3","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1016\/j.jcss.2009.04.001","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. J. Comput. Syst. Sci.\u00a075, 423\u2013434 (2009)","journal-title":"J. Comput. Syst. Sci."},{"key":"30_CR4","doi-asserted-by":"crossref","unstructured":"Guo, J., Niedermeier, R.: Linear problem kernels for NP-hard problems on planar graphs. In: Proc. 34th ICALP, pp. 375\u2013386 (2007)","DOI":"10.1007\/978-3-540-73420-8_34"},{"key":"30_CR5","doi-asserted-by":"crossref","unstructured":"Bodlaender, H.L., Fomin, F.V., Lokshtanov, D., Penninkx, E., Saurabh, S., Thilikos, D.M.: (Meta) Kernelization. In: Proc. 50th FOCS, pp. 629\u2013638 (2009)","DOI":"10.1109\/FOCS.2009.46"},{"key":"30_CR6","doi-asserted-by":"crossref","unstructured":"Fomin, F., Lokshtanov, D., Saurabh, S., Thilikos, D.M.: Bidimensionality and kernels. In: Proc. 21st SODA, pp. 503\u2013510 (2010)","DOI":"10.1137\/1.9781611973075.43"},{"key":"30_CR7","unstructured":"van Leeuwen, E.J.: Optimization and Approximation on Systems of Geometric Objects. PhD thesis, CWI Amsterdam (2009)"},{"key":"30_CR8","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1016\/0012-365X(90)90358-O","volume":"86","author":"B.N. Clark","year":"1990","unstructured":"Clark, B.N., Colbourn, C.J., Johnson, D.S.: Unit disk graphs. Discrete Mathematics\u00a086, 165\u2013177 (1990)","journal-title":"Discrete Mathematics"},{"key":"30_CR9","doi-asserted-by":"crossref","unstructured":"Marx, D.: Efficient approximation schemes for geometric problems? In: Proc. 13th ESA, pp. 448\u2013459 (2005)","DOI":"10.1007\/11561071_41"},{"key":"30_CR10","doi-asserted-by":"crossref","unstructured":"Marx, D.: Parameterized complexity of independence and domination on geometric graphs. In: Proc. 2nd IWPEC, pp. 154\u2013165 (2006)","DOI":"10.1007\/11847250_14"},{"key":"30_CR11","doi-asserted-by":"publisher","first-page":"134","DOI":"10.1016\/j.jalgor.2003.10.001","volume":"52","author":"J. Alber","year":"2004","unstructured":"Alber, J., Fiala, J.: Geometric separation and exact solutions for the parameterized independent set problem on disk graphs. J. Algorithms\u00a052, 134\u2013151 (2004)","journal-title":"J. Algorithms"},{"key":"30_CR12","doi-asserted-by":"crossref","unstructured":"Philip, G., Raman, V., Sikdar, S.: Solving dominating set in larger classes of graphs: Fpt algorithms and polynomial kernels. In: Proc. 17th ESA, pp. 694\u2013705 (2009)","DOI":"10.1007\/978-3-642-04128-0_62"},{"key":"30_CR13","doi-asserted-by":"crossref","unstructured":"Dom, M., Lokshtanov, D., Saurabh, S.: Incompressibility through colors and ids. In: Proc. 36th ICALP, pp. 378\u2013389 (2009)","DOI":"10.1007\/978-3-642-02927-1_32"},{"key":"30_CR14","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1002\/net.3230250205","volume":"25","author":"M. Marathe","year":"1995","unstructured":"Marathe, M., Breu, H., Iii, H.B.H., Ravi, S.S., Rosenkrantz, D.J.: Simple heuristics for unit disk graphs. Networks\u00a025, 59\u201368 (1995)","journal-title":"Networks"},{"key":"30_CR15","doi-asserted-by":"crossref","unstructured":"Wiese, A., Kranakis, E.: Local PTAS for independent set and vertex cover in location aware unit disk graphs. In: Proc. 4th DCOSS, pp. 415\u2013431 (2008)","DOI":"10.1007\/978-3-540-69170-9_28"},{"key":"30_CR16","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1016\/j.endm.2008.06.056","volume":"31","author":"J. Kratochv\u00edl","year":"2008","unstructured":"Kratochv\u00edl, J., Pergel, M.: Intersection graphs of homothetic polygons. Electronic Notes in Discrete Mathematics 31, 277\u2013280 (2008)","journal-title":"Electronic Notes in Discrete Mathematics"},{"key":"30_CR17","doi-asserted-by":"crossref","unstructured":"Moser, H.: A problem kernelization for graph packing. In: Proc. 35th SOFSEM, pp. 401\u2013412 (2009)","DOI":"10.1007\/978-3-540-95891-8_37"},{"key":"30_CR18","doi-asserted-by":"publisher","first-page":"238","DOI":"10.1006\/jagm.1997.0903","volume":"26","author":"H.B. Hunt","year":"1998","unstructured":"Hunt, H.B., Marathe, M.V., Radhakrishnan, V., Ravi, S.S., Rosenkrantz, D.J., Stearns, R.E.: NC-approximation schemes for NP- and PSPACE-hard problems for geometric graphs. Journal of Algorithms\u00a026, 238\u2013274 (1998)","journal-title":"Journal of Algorithms"},{"key":"30_CR19","doi-asserted-by":"crossref","unstructured":"Chan, T.M., Har-Peled, S.: Approximation algorithms for maximum independent set of pseudo-disks. In: Proceedings 25th SCG, pp. 333\u2013340 (2009)","DOI":"10.1145\/1542362.1542420"},{"key":"30_CR20","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1016\/0925-7721(94)90003-5","volume":"4","author":"A. Efrat","year":"1994","unstructured":"Efrat, A., Sharir, M., Ziv, A.: Computing the smallest k-enclosing circle and related problems. Comput. Geom.\u00a04, 119\u2013136 (1994)","journal-title":"Comput. Geom."},{"key":"30_CR21","doi-asserted-by":"crossref","unstructured":"de Berg, M., Speckmann, B.: Computational geometry: Fundamental structures. In: Handbook of Data Structures and Applications, pp. 62.1\u201362.20 (2004)","DOI":"10.1201\/9781420035179.ch62"}],"container-title":["Lecture Notes in Computer Science","Algorithm Theory - SWAT 2010"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-13731-0_30.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,24]],"date-time":"2020-11-24T02:42:22Z","timestamp":1606185742000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-13731-0_30"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642137303","9783642137310"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-13731-0_30","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}