{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T03:19:36Z","timestamp":1725851976233},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662495285"},{"type":"electronic","value":"9783662495292"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-662-49529-2_8","type":"book-chapter","created":{"date-parts":[[2016,3,21]],"date-time":"2016-03-21T08:09:41Z","timestamp":1458547781000},"page":"96-109","source":"Crossref","is-referenced-by-count":0,"title":["Parameterized Complexity of Red Blue Set Cover for Lines"],"prefix":"10.1007","author":[{"given":"Pradeesha","family":"Ashok","sequence":"first","affiliation":[]},{"given":"Sudeshna","family":"Kolay","sequence":"additional","affiliation":[]},{"given":"Saket","family":"Saurabh","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,3,22]]},"reference":[{"issue":"8","key":"8_CR1","doi-asserted-by":"publisher","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":"8_CR2","unstructured":"Carr, R.D., Doddi, S., Konjevod, G., Marathe, M.V.: On the red-blue set cover problem. In: SODA, vol. 9, pp. 345\u2013353 (2000)"},{"key":"8_CR3","unstructured":"Chan, T.M., Hu, N.: Geometric red-blue set cover for unit squares and related problems. In: CCCG (2013)"},{"issue":"5","key":"8_CR4","doi-asserted-by":"publisher","first-page":"651","DOI":"10.1109\/32.6142","volume":"14","author":"S Ying Cheng","year":"1988","unstructured":"Ying Cheng, S., Iyengar, S., Kashyap, R.L.: A new method of image compression using irreducible covers of maximal rectangles. IEEE Trans. Software Eng. 14(5), 651\u2013658 (1988)","journal-title":"IEEE Trans. Software Eng."},{"issue":"3","key":"8_CR5","doi-asserted-by":"publisher","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":"8_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2650261","volume":"11","author":"M Dom","year":"2014","unstructured":"Dom, M., Lokshtanov, D., Saurabh, S.: Kernelization lower bounds through colors, ids. ACM Trans. Algorithms 11(2), 1\u201320 (2014)","journal-title":"ACM Trans. Algorithms"},{"key":"8_CR7","doi-asserted-by":"publisher","first-page":"530","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, p. 530. Springer-Verlag, Heidelberg (1999)"},{"key":"8_CR8","series-title":"Texts in Theoretical Computer Science. An EATCS Series","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, Heidelberg (2006)"},{"issue":"1","key":"8_CR9","doi-asserted-by":"publisher","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."},{"key":"8_CR10","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of Computer Computations","author":"Richard M. Karp","year":"1972","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Proceedings of a Symposium on the Complexity of Computer Computations, pp. 85\u2013103 (1972)"},{"key":"8_CR11","doi-asserted-by":"crossref","unstructured":"Kratsch, S., Philip, G., Ray, S.: Point line cover: The easy kernel is essentially tight. In: SODA, pp. 1596\u20131606 (2014)","DOI":"10.1137\/1.9781611973402.116"},{"key":"8_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"624","DOI":"10.1007\/3-540-45022-X_53","volume-title":"Automata, Languages and Programming","author":"VSA Kumar","year":"2000","unstructured":"Kumar, V.S.A., Arya, S., Ramesh, H.: Hardness of set cover with intersection 1. In: Welzl, E., Montanari, U., Rolim, J.D.P. (eds.) ICALP 2000. LNCS, vol. 1853, pp. 624\u2013635. Springer, Heidelberg (2000)"},{"issue":"4","key":"8_CR13","doi-asserted-by":"publisher","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":"8_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1007\/3-540-18625-5_45","volume-title":"Foundations of Software Technology and Theoretical Computer Science","author":"C Levcopoulos","year":"1987","unstructured":"Levcopoulos, C.: Improved bounds for covering general polygons with rectangles. In: Nori, K.V. (ed.) FSTTCS 1987. LNCS, vol. 287, pp. 95\u2013102. Springer, Heidelberg (1987)"},{"key":"8_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"154","DOI":"10.1007\/11847250_14","volume-title":"Parameterized and Exact Computation","author":"D Marx","year":"2006","unstructured":"Marx, D.: Parameterized complexity of independence and domination on geometric graphs. In: Bodlaender, H.L., Langston, M.A. (eds.) IWPEC 2006. LNCS, vol. 4169, pp. 154\u2013165. Springer, Heidelberg (2006)"},{"key":"8_CR16","first-page":"79","volume":"77","author":"L Mathieson","year":"2008","unstructured":"Mathieson, L., Szeider, S.: The parameterized complexity of regular subgraph problems and generalizations. CATS 77, 79\u201386 (2008)","journal-title":"CATS"},{"issue":"1","key":"8_CR17","doi-asserted-by":"publisher","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                    \n                      \n                    \n                    $${}_{\\text{ max }}$$\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":"8_CR18","doi-asserted-by":"publisher","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"}],"container-title":["Lecture Notes in Computer Science","LATIN 2016: Theoretical Informatics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-49529-2_8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,1]],"date-time":"2019-06-01T20:28:18Z","timestamp":1559420898000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-49529-2_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783662495285","9783662495292"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-49529-2_8","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]}}}