{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,10]],"date-time":"2025-11-10T21:00:46Z","timestamp":1762808446900,"version":"3.37.3"},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2016,10,3]],"date-time":"2016-10-03T00:00:00Z","timestamp":1475452800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["306992"],"award-info":[{"award-number":["306992"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2017,11]]},"DOI":"10.1007\/s00453-016-0216-x","type":"journal-article","created":{"date-parts":[[2016,10,3]],"date-time":"2016-10-03T10:37:59Z","timestamp":1475491079000},"page":"667-697","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Multivariate Complexity Analysis of Geometric Red Blue Set Cover"],"prefix":"10.1007","volume":"79","author":[{"given":"Pradeesha","family":"Ashok","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2975-4856","authenticated-orcid":false,"given":"Sudeshna","family":"Kolay","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Saket","family":"Saurabh","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,10,3]]},"reference":[{"key":"216_CR1","unstructured":"Advanced methods for medicare fraud waste and abuse detection project. Los Alamos National Laboratory, Internal report, June (1998)"},{"issue":"8","key":"216_CR2","doi-asserted-by":"crossref","first-page":"423","DOI":"10.1016\/j.jcss.2009.04.001","volume":"75","author":"HL Bodlaender","year":"2009","unstructured":"Bodlaender, H.L., Downey, R.G., Fellows, M.R., Hermelin, D.: On problems without polynomial kernels. J. Comput. Syst. Sci. 75(8), 423\u2013434 (2009)","journal-title":"J. Comput. Syst. Sci."},{"key":"216_CR3","unstructured":"Carr, R.D., Doddi, S., Konjevod, G., Marathe, M.V.: On the red-blue set cover problem. In: Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, vol. 9, pp. 345\u2013353 (2000)"},{"issue":"5","key":"216_CR4","doi-asserted-by":"crossref","first-page":"380","DOI":"10.1016\/j.comgeo.2014.12.005","volume":"48","author":"TM Chan","year":"2015","unstructured":"Chan, T.M., Hu, N.: Geometric red-blue set cover for unit squares and related problems. Comput. Geom. 48(5), 380\u2013385 (2015)","journal-title":"Comput. Geom."},{"issue":"6","key":"216_CR5","doi-asserted-by":"crossref","first-page":"866","DOI":"10.1145\/1101821.1101823","volume":"52","author":"ED Demaine","year":"2005","unstructured":"Demaine, E.D., Fomin, F.V., Hajiaghayi, M.T., Thilikos, D.M.: Subexponential parameterized algorithms on bounded-genus graphs and H-minor-free graphs. J. ACM 52(6), 866\u2013893 (2005)","journal-title":"J. ACM"},{"issue":"3","key":"216_CR6","doi-asserted-by":"crossref","first-page":"393","DOI":"10.1016\/j.jda.2007.11.002","volume":"6","author":"M Dom","year":"2008","unstructured":"Dom, M., Guo, J., Niedermeier, R., Wernicke, S.: Red-blue covering problems and the consecutive ones property. J. Discrete Algorithms 6(3), 393\u2013407 (2008)","journal-title":"J. Discrete Algorithms"},{"issue":"2","key":"216_CR7","first-page":"13:1","volume":"11","author":"M Dom","year":"2014","unstructured":"Dom, M., Lokshtanov, D., Saurabh, S.: Kernelization lower bounds through colors and ids. ACM Trans. Algorithms 11(2), 13:1\u201313:20 (2014)","journal-title":"ACM Trans. Algorithms"},{"key":"216_CR8","doi-asserted-by":"crossref","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 City (1999). 530 pp"},{"issue":"2","key":"216_CR9","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1007\/s00453-007-9146-y","volume":"52","author":"MR Fellows","year":"2008","unstructured":"Fellows, M.R., Knauer, C., Nishimura, N., Ragde, P., Rosamond, Frances A., Stege, Ulrike, Thilikos, Dimitrios M., Whitesides, Sue: Faster fixed-parameter tractable algorithms for matching and packing problems. Algorithmica 52(2), 167\u2013176 (2008)","journal-title":"Algorithmica"},{"key":"216_CR10","volume-title":"Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series","author":"J Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series. Springer, Berlin (2006)"},{"issue":"2","key":"216_CR11","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1007\/s00453-007-9133-3","volume":"54","author":"FV Fomin","year":"2009","unstructured":"Fomin, F.V., Gaspers, S., Saurabh, S., Stepanov, A.A.: On two techniques of combining branching and treewidth. Algorithmica 54(2), 181\u2013207 (2009)","journal-title":"Algorithmica"},{"issue":"1","key":"216_CR12","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1016\/j.jcss.2010.06.007","volume":"77","author":"L Fortnow","year":"2011","unstructured":"Fortnow, L., Santhanam, R.: Infeasibility of instance compression and succinct pcps for NP. J. Comput. Syst. Sci. 77(1), 91\u2013106 (2011)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"216_CR13","doi-asserted-by":"crossref","first-page":"512","DOI":"10.1006\/jcss.2001.1774","volume":"63","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? J. Comput. Syst. Sci. 63(4), 512\u2013530 (2001)","journal-title":"J. Comput. Syst. Sci."},{"key":"216_CR14","doi-asserted-by":"crossref","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Proceedings of a Symposium on the Complexity of Computer Computations, pp. 85\u2013103 (1972)","DOI":"10.1007\/978-1-4684-2001-2_9"},{"issue":"3","key":"216_CR15","doi-asserted-by":"crossref","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. ACM Trans. Algorithms 12(3), 40 (2016)","journal-title":"ACM Trans. Algorithms"},{"issue":"4","key":"216_CR16","doi-asserted-by":"crossref","first-page":"717","DOI":"10.1007\/s00454-004-1108-4","volume":"33","author":"S Langerman","year":"2005","unstructured":"Langerman, S., Morin, P.: Covering things with things. Discrete Comput. Geom. 33(4), 717\u2013729 (2005)","journal-title":"Discrete Comput. Geom."},{"key":"216_CR17","doi-asserted-by":"crossref","unstructured":"Marx, D.: Efficient approximation schemes for geometric problems? In: Proceedings of 13th Annual European Symposium on Algorithms, pp. 448\u2013459. Springer (2005)","DOI":"10.1007\/11561071_41"},{"key":"216_CR18","doi-asserted-by":"crossref","unstructured":"Marx, D.: Parameterized complexity of independence and domination on geometric graphs. In: Parameterized and Exact Computation, pp. 154\u2013165. Springer (2006)","DOI":"10.1007\/11847250_14"},{"key":"216_CR19","unstructured":"Mathieson, L., Szeider, S.: The parameterized complexity of regular subgraph problems and generalizations. In: Proceedings of the Fourteenth Symposium on Computing: the Australasian Theory, vol. 77, pp. 79\u201386 (2008)"},{"issue":"1","key":"216_CR20","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1016\/j.jda.2006.03.008","volume":"5","author":"D Peleg","year":"2007","unstructured":"Peleg, D.: Approximation algorithms for the label-cover\n                        $$_{\\text{ max }}$$\n                        \n                            \n                                            \n                                \n                                    \n                                    \n                                        \n                                        max\n                                        \n                                    \n                                \n                            \n                        \n                     and red-blue set cover problems. J. Discrete Algorithms 5(1), 55\u201364 (2007)","journal-title":"J. Discrete Algorithms"},{"issue":"2","key":"216_CR21","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1007\/s00453-007-9148-9","volume":"52","author":"V Raman","year":"2008","unstructured":"Raman, V., Saurabh, S.: Short cycles make W-hard problems hard: FPT algorithms for W-hard problems in graphs with no short cycles. Algorithmica 52(2), 203\u2013225 (2008)","journal-title":"Algorithmica"},{"issue":"1","key":"216_CR22","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1016\/0095-8956(84)90013-3","volume":"36","author":"N Robertson","year":"1984","unstructured":"Robertson, N., Seymou, P.D.: Graph minors III planar tree-width. J. Comb. Theory Ser. B 36(1), 49\u201364 (1984)","journal-title":"J. Comb. Theory Ser. B"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-016-0216-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0216-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0216-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,9,11]],"date-time":"2017-09-11T18:25:23Z","timestamp":1505154323000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-016-0216-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,10,3]]},"references-count":22,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2017,11]]}},"alternative-id":["216"],"URL":"https:\/\/doi.org\/10.1007\/s00453-016-0216-x","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2016,10,3]]}}}