{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,10]],"date-time":"2024-09-10T12:27:11Z","timestamp":1725971231012},"publisher-location":"Cham","reference-count":20,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319774039"},{"type":"electronic","value":"9783319774046"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"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":[[2018]]},"DOI":"10.1007\/978-3-319-77404-6_15","type":"book-chapter","created":{"date-parts":[[2018,3,12]],"date-time":"2018-03-12T10:03:11Z","timestamp":1520848991000},"page":"187-200","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Tight Kernels for Covering and Hitting: Point Hyperplane Cover and\u00a0Polynomial Point Hitting Set"],"prefix":"10.1007","author":[{"given":"Jean-Daniel","family":"Boissonnat","sequence":"first","affiliation":[]},{"given":"Kunal","family":"Dutta","sequence":"additional","affiliation":[]},{"given":"Arijit","family":"Ghosh","sequence":"additional","affiliation":[]},{"given":"Sudeshna","family":"Kolay","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,3,13]]},"reference":[{"key":"15_CR1","unstructured":"Afshani, P., Berglin, E., van Duijn, I., Nielsen, J.S.: Applications of incidence bounds in point covering problems. In: SoCG, pp. 60:1\u201360:15 (2016)"},{"issue":"1\u20132","key":"15_CR2","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1016\/S0304-3975(98)00158-3","volume":"237","author":"P Alimonti","year":"2000","unstructured":"Alimonti, P., Kann, V.: Some APX-completeness results for cubic graphs. TCS 237(1\u20132), 123\u2013134 (2000)","journal-title":"TCS"},{"key":"15_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"548","DOI":"10.1007\/978-3-319-21398-9_43","volume-title":"Computing and Combinatorics","author":"P Ashok","year":"2015","unstructured":"Ashok, P., Kolay, S., Misra, N., Saurabh, S.: Unique covering problems with geometric sets. In: Xu, D., Du, D., Du, D. (eds.) COCOON 2015. LNCS, vol. 9198, pp. 548\u2013558. Springer, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-21398-9_43"},{"key":"15_CR4","first-page":"1","volume":"79","author":"P Ashok","year":"2015","unstructured":"Ashok, P., Kolay, S., Saurabh, S.: Multivariate complexity analysis of geometric red blue set cover. Algorithmica 79, 1\u201331 (2015)","journal-title":"Algorithmica"},{"key":"15_CR5","unstructured":"Boissonnat, J., Dutta, K., Ghosh, A., Kolay, S.: Kernelization of the subset general position problem in geometry. In: MFCS, pp. 25:1\u201325:13 (2017)"},{"key":"15_CR6","unstructured":"Bringmann, K., Kozma, L., Moran, S., Narayanaswamy, N.S.: Hitting set for hypergraphs of low VC-dimension. In: ESA, pp. 23:1\u201323:18 (2016)"},{"key":"15_CR7","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized Algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., Fomin, F.V., Kowalik, \u0141., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms, vol. 3. Springer, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-21275-3"},{"key":"15_CR8","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":"15_CR9","doi-asserted-by":"crossref","unstructured":"Dinur, I., Steurer, D.: Analytical approach to parallel repetition. In: STOC, pages 624\u2013633. ACM (2014)","DOI":"10.1145\/2591796.2591884"},{"key":"15_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"298","DOI":"10.1007\/978-3-642-00202-1_26","volume-title":"WALCOM: Algorithms and Computation","author":"M Dom","year":"2009","unstructured":"Dom, M., Fellows, M.R., Rosamond, F.A.: Parameterized complexity of stabbing rectangles and squares in the plane. In: Das, S., Uehara, R. (eds.) WALCOM 2009. LNCS, vol. 5431, pp. 298\u2013309. Springer, Heidelberg (2009). https:\/\/doi.org\/10.1007\/978-3-642-00202-1_26"},{"key":"15_CR11","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"RG Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, New York (1999). https:\/\/doi.org\/10.1007\/978-1-4612-0515-9. 530 p."},{"key":"15_CR12","series-title":"Texts in Theoretical Computer Science. An EATCS Series","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-29953-X","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. Springer-Verlag, New York Inc., Secaucus (2006). https:\/\/doi.org\/10.1007\/3-540-29953-X"},{"issue":"3","key":"15_CR13","doi-asserted-by":"publisher","first-page":"372","DOI":"10.1093\/comjnl\/bxm053","volume":"51","author":"P Giannopoulos","year":"2008","unstructured":"Giannopoulos, P., Knauer, C., Whitesides, S.: Parameterized complexity of geometric problems. Comput. J. 51(3), 372\u2013384 (2008)","journal-title":"Comput. J."},{"key":"15_CR14","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/j.ic.2013.08.007","volume":"231","author":"P Heggernes","year":"2013","unstructured":"Heggernes, P., Kratsch, D., Lokshtanov, D., Raman, V., Saurabh, S.: Fixed-parameter algorithms for cochromatic number and disjoint rectangle stabbing via iterative localization. Inf. Comput. 231, 109\u2013116 (2013)","journal-title":"Inf. Comput."},{"key":"15_CR15","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1007\/978-3-540-68279-0_8","volume-title":"50 Years of Integer Programming 1958\u20132008 - From the Early Years to the State-of-the-Art","author":"RM Karp","year":"2010","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: J\u00fcnger, M., et al. (eds.) 50 Years of Integer Programming 1958\u20132008 - From the Early Years to the State-of-the-Art, pp. 219\u2013241. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-540-68279-0_8"},{"issue":"3","key":"15_CR16","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1145\/2832912","volume":"12","author":"S Kratsch","year":"2016","unstructured":"Kratsch, S., Philip, G., Ray, S.: Point line cover: the easy kernel is essentially tight. TALG 12(3), 40 (2016)","journal-title":"TALG"},{"issue":"4","key":"15_CR17","first-page":"717","volume":"33","author":"S Langerman","year":"2005","unstructured":"Langerman, S., Morin, P.: Covering things with things. DCG 33(4), 717\u2013729 (2005)","journal-title":"DCG"},{"key":"15_CR18","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-0039-7","volume-title":"Lectures on Discrete Geometry","author":"J Matou\u0161ek","year":"2002","unstructured":"Matou\u0161ek, J.: Lectures on Discrete Geometry, vol. 212. Springer Science & Business Media, New York (2002). https:\/\/doi.org\/10.1007\/978-1-4613-0039-7"},{"issue":"5","key":"15_CR19","doi-asserted-by":"publisher","first-page":"194","DOI":"10.1016\/0167-6377(82)90039-6","volume":"1","author":"N Megiddo","year":"1982","unstructured":"Megiddo, N., Tamir, A.: On the complexity of locating linear facilities in the plane. Oper. Res. Lett. 1(5), 194\u2013197 (1982)","journal-title":"Oper. Res. Lett."},{"key":"15_CR20","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-04565-7","volume-title":"Approximation Algorithms","author":"VV Vazirani","year":"2013","unstructured":"Vazirani, V.V.: Approximation Algorithms. Springer Science & Business Media, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-662-04565-7"}],"container-title":["Lecture Notes in Computer Science","LATIN 2018: Theoretical Informatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-77404-6_15","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,7]],"date-time":"2024-03-07T16:01:43Z","timestamp":1709827303000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-77404-6_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783319774039","9783319774046"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-77404-6_15","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2018]]},"assertion":[{"value":"13 March 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"LATIN","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Latin American Symposium on Theoretical Informatics","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Buenos Aires","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Argentina","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2018","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"16 April 2018","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"19 April 2018","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"13","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"latin2018","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/latin2018.dc.uba.ar\/#","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}