{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,29]],"date-time":"2026-05-29T11:14:12Z","timestamp":1780053252842,"version":"3.54.0"},"reference-count":39,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2019,7,11]],"date-time":"2019-07-11T00:00:00Z","timestamp":1562803200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,7,11]],"date-time":"2019-07-11T00:00:00Z","timestamp":1562803200000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100011199","name":"FP7 Ideas: European Research Council","doi-asserted-by":"publisher","award":["306992"],"award-info":[{"award-number":["306992"]}],"id":[{"id":"10.13039\/100011199","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2020,1]]},"DOI":"10.1007\/s00453-019-00600-w","type":"journal-article","created":{"date-parts":[[2019,7,11]],"date-time":"2019-07-11T13:14:11Z","timestamp":1562850851000},"page":"1-19","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Parameterized Complexity of Geometric Covering Problems Having Conflicts"],"prefix":"10.1007","volume":"82","author":[{"given":"Aritra","family":"Banik","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Fahad","family":"Panolan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Venkatesh","family":"Raman","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Vibha","family":"Sahlot","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7847-6402","authenticated-orcid":false,"given":"Saket","family":"Saurabh","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2019,7,11]]},"reference":[{"key":"600_CR1","doi-asserted-by":"publisher","first-page":"318","DOI":"10.1007\/978-3-662-48971-0_28","volume-title":"Algorithms and Computation","author":"Esther M. Arkin","year":"2015","unstructured":"Arkin, E.M., Banik, A., Carmi, P., Citovsky, G., Katz, M.J., Mitchell, J.S.B., Simakov, M.: Choice is hard. In: Proc. 26th Internat. Sympos. Algorithms and Computation, ISAAC 2015, pp. 318\u2013328 (2015). \nhttps:\/\/doi.org\/10.1007\/978-3-662-48971-0_28"},{"key":"600_CR2","unstructured":"Arkin, E.M., Banik, A., Carmi, P., Citovsky, G., Katz, M.J., Mitchell, J.S.B., Simakov, M.: Conflict-free covering. In: Proc. 27th Canadian Conf. on Comput. Geom., CCCG 2015 (2015)"},{"issue":"2","key":"600_CR3","doi-asserted-by":"publisher","first-page":"94","DOI":"10.1016\/j.comgeo.2014.08.004","volume":"48","author":"EM Arkin","year":"2015","unstructured":"Arkin, E.M., D\u00edaz-B\u00e1\u00f1ez, J.M., Hurtado, F., Kumar, P., Mitchell, J.S.B., Palop, B., P\u00e9rez-Lantero, P., Saumell, M., Silveira, R.I.: Bichromatic 2-center of pairs of points. Comput. Geom. 48(2), 94\u2013107 (2015). \nhttps:\/\/doi.org\/10.1016\/j.comgeo.2014.08.004","journal-title":"Comput. Geom."},{"issue":"3","key":"600_CR4","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1002\/1097-0037(200010)36:3<147::AID-NET1>3.0.CO;2-M","volume":"36","author":"EM Arkin","year":"2000","unstructured":"Arkin, E.M., Hassin, R.: Minimum-diameter covering problems. Networks 36(3), 147\u2013155 (2000)","journal-title":"Networks"},{"issue":"2","key":"600_CR5","doi-asserted-by":"publisher","first-page":"543","DOI":"10.1137\/120891241","volume":"43","author":"B Aronov","year":"2014","unstructured":"Aronov, B., de Berg, M., Ezra, E., Sharir, M.: Improved bounds for the union of locally fat objects in the plane. SIAM J. Comput. 43(2), 543\u2013572 (2014)","journal-title":"SIAM J. Comput."},{"issue":"9","key":"600_CR6","doi-asserted-by":"publisher","first-page":"2616","DOI":"10.1007\/s00453-017-0352-y","volume":"80","author":"A Banik","year":"2018","unstructured":"Banik, A., Panolan, F., Raman, V., Sahlot, V.: Fr\u00e9chet distance between a line and avatar point set. Algorithmica 80(9), 2616\u20132636 (2018). \nhttps:\/\/doi.org\/10.1007\/s00453-017-0352-y","journal-title":"Algorithmica"},{"key":"600_CR7","doi-asserted-by":"publisher","unstructured":"Bonnet, \u00c9., Miltzow, T.: An approximation algorithm for the art gallery problem. In: 33rd International Symposium on Computational Geometry, SoCG 2017, 4\u20137 July 2017, Brisbane, Australia, pp. 20:1\u201320:15 (2017). \nhttps:\/\/doi.org\/10.4230\/LIPIcs.SoCG.2017.20","DOI":"10.4230\/LIPIcs.SoCG.2017.20"},{"issue":"4","key":"600_CR8","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1007\/BF02570718","volume":"14","author":"H Br\u00f6nnimann","year":"1995","unstructured":"Br\u00f6nnimann, H., Goodrich, M.T.: Almost optimal set covers in finite VC-dimension. Discrete Comput. Geom. 14(4), 463\u2013479 (1995)","journal-title":"Discrete Comput. Geom."},{"issue":"2","key":"600_CR9","doi-asserted-by":"publisher","first-page":"178","DOI":"10.1016\/S0196-6774(02)00294-8","volume":"46","author":"TM Chan","year":"2003","unstructured":"Chan, T.M.: Polynomial-time approximation schemes for packing and piercing fat objects. J. Algorithms 46(2), 178\u2013189 (2003)","journal-title":"J. Algorithms"},{"issue":"1","key":"600_CR10","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1007\/s00454-006-1273-8","volume":"37","author":"KL Clarkson","year":"2007","unstructured":"Clarkson, K.L., Varadarajan, K.R.: Improved approximation algorithms for geometric set cover. Discrete Comput. Geom. 37(1), 43\u201358 (2007)","journal-title":"Discrete Comput. Geom."},{"key":"600_CR11","doi-asserted-by":"publisher","unstructured":"Consuegra, M.E., Narasimhan, G.: Geometric avatar problems. In: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2013, LIPIcs, vol. 24, pp. 389\u2013400 (2013). \nhttps:\/\/doi.org\/10.4230\/LIPIcs.FSTTCS.2013.389","DOI":"10.4230\/LIPIcs.FSTTCS.2013.389"},{"key":"600_CR12","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, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, Berlin (2015)"},{"issue":"6","key":"600_CR13","doi-asserted-by":"publisher","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). \nhttps:\/\/doi.org\/10.1145\/1101821.1101823","journal-title":"J. ACM"},{"key":"600_CR14","volume-title":"Graph Theory. Graduate Texts in Mathematics","author":"R Diestel","year":"2012","unstructured":"Diestel, R.: Graph Theory. Graduate Texts in Mathematics, vol. 173, 4th edn. Springer, Berlin (2012)","edition":"4"},{"key":"600_CR15","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-5559-1","volume-title":"Fundamentals of Parameterized Complexity","author":"R Downey","year":"2013","unstructured":"Downey, R., Fellows, M.: Fundamentals of Parameterized Complexity. Springer, Berlin (2013)"},{"key":"600_CR16","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, Berlin (1999)"},{"key":"600_CR17","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511808241","volume-title":"How to Think About Algorithms","author":"J Edmonds","year":"2008","unstructured":"Edmonds, J.: How to Think About Algorithms. Cambridge University Press, New York (2008)"},{"issue":"2","key":"600_CR18","doi-asserted-by":"publisher","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, F.A., Stege, U., Thilikos, D.M., Whitesides, S.: Faster fixed-parameter tractable algorithms for matching and packing problems. Algorithmica 52(2), 167\u2013176 (2008). \nhttps:\/\/doi.org\/10.1007\/s00453-007-9146-y","journal-title":"Algorithmica"},{"key":"600_CR19","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":"600_CR20","doi-asserted-by":"publisher","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). \nhttps:\/\/doi.org\/10.1007\/s00453-007-9133-3","journal-title":"Algorithmica"},{"issue":"4","key":"600_CR21","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1145\/2886094","volume":"63","author":"FV Fomin","year":"2016","unstructured":"Fomin, F.V., Lokshtanov, D., Panolan, F., Saurabh, S.: Efficient computation of representative families with applications in parameterized and exact algorithms. J. ACM 63(4), 29 (2016)","journal-title":"J. ACM"},{"issue":"3","key":"600_CR22","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1109\/TSE.1976.233819","volume":"2","author":"HN Gabow","year":"1976","unstructured":"Gabow, H.N., Maheshwari, S.N., Osterweil, L.J.: On two problems in the generation of program test paths. IEEE Trans. Softw. Eng. 2(3), 227\u2013231 (1976)","journal-title":"IEEE Trans. Softw. Eng."},{"issue":"5&6","key":"600_CR23","doi-asserted-by":"publisher","first-page":"465","DOI":"10.1007\/BF01758774","volume":"7","author":"HN Gabow","year":"1992","unstructured":"Gabow, H.N., Westermann, H.H.: Forests, frames, and games: algorithms for matroid sums and applications. Algorithmica 7(5&6), 465\u2013497 (1992)","journal-title":"Algorithmica"},{"key":"600_CR24","unstructured":"Har-Peled, S., Quanrud, K.: Approximation algorithms for low-density graphs (2015). CoRR \narXiv:1501.00721"},{"key":"600_CR25","doi-asserted-by":"crossref","unstructured":"Har-Peled, S., Quanrud, K.: Approximation algorithms for polynomial-expansion and low-density graphs. In: Algorithms\u2014ESA 2015\u201423rd Annual European Symposium, Patras, Greece, 14\u201316 September 2015, Proceedings, vol. 9294, pp. 717\u2013728. Springer (2015)","DOI":"10.1007\/978-3-662-48350-3_60"},{"key":"600_CR26","doi-asserted-by":"publisher","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)"},{"issue":"3","key":"600_CR27","doi-asserted-by":"publisher","first-page":"40:1","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:1\u201340:16 (2016). \nhttps:\/\/doi.org\/10.1145\/2832912","journal-title":"ACM Trans. Algorithms"},{"issue":"1","key":"600_CR28","first-page":"168","volume":"5","author":"E Krohn","year":"2014","unstructured":"Krohn, E., Gibson, M., Kanade, G., Varadarajan, K.R.: Guarding terrains via local search. JoCG 5(1), 168\u2013178 (2014)","journal-title":"JoCG"},{"issue":"4","key":"600_CR29","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":"600_CR30","unstructured":"Liu, C., Veeraraghavan, K., Iyengar, V.: Thermal-aware test scheduling and hot spot temperature minimization for core-based systems. In: 20th IEEE International Symposium on Defect and Fault Tolerance in VLSI Systems (DFT\u201905), pp. 552\u2013560. IEEE (2005)"},{"issue":"2","key":"600_CR31","doi-asserted-by":"publisher","first-page":"14:1","DOI":"10.1145\/3170444","volume":"14","author":"D Lokshtanov","year":"2018","unstructured":"Lokshtanov, D., Misra, P., Panolan, F., Saurabh, S.: Deterministic truncation of linear matroids. ACM Trans. Algorithms 14(2), 14:1\u201314:20 (2018). \nhttps:\/\/doi.org\/10.1145\/3170444","journal-title":"ACM Trans. Algorithms"},{"key":"600_CR32","doi-asserted-by":"publisher","unstructured":"Lokshtanov, D., Panolan, F., Ramanujan, M.S., Saurabh, S.: Lossy kernelization. In: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, 19-23 June 2017, pp. 224\u2013237 (2017). \nhttps:\/\/doi.org\/10.1145\/3055399.3055456","DOI":"10.1145\/3055399.3055456"},{"key":"600_CR33","doi-asserted-by":"crossref","unstructured":"Marx, D.: Efficient approximation schemes for geometric problems? In: ESA, pp. 448\u2013459. Springer (2005)","DOI":"10.1007\/11561071_41"},{"issue":"44","key":"600_CR34","doi-asserted-by":"publisher","first-page":"4471","DOI":"10.1016\/j.tcs.2009.07.027","volume":"410","author":"D Marx","year":"2009","unstructured":"Marx, D.: A parameterized view on matroid optimization problems. Theor. Comput. Sci. 410(44), 4471\u20134479 (2009)","journal-title":"Theor. Comput. Sci."},{"key":"600_CR35","doi-asserted-by":"crossref","unstructured":"Mustafa, N.H., Raman, R., Ray, S.: Settling the APX-hardness status for geometric set cover. In: 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, pp. 541\u2013550. IEEE Computer Society (2014)","DOI":"10.1109\/FOCS.2014.64"},{"key":"600_CR36","unstructured":"Naor, M., Schulman, J.L., Srinivasan, A.: Splitters and near-optimal derandomization. In: FOCS, pp. 182\u2013191 (1995)"},{"key":"600_CR37","volume-title":"Matroid Theory","author":"JG Oxley","year":"2006","unstructured":"Oxley, J.G.: Matroid Theory, vol. 3. Oxford University Press, Oxford (2006)"},{"issue":"2","key":"600_CR38","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"},{"key":"600_CR39","doi-asserted-by":"crossref","unstructured":"Williams, V.V.: Multiplying matrices faster than Coppersmith-Winograd. pp. 887\u2013898. ACM (2012)","DOI":"10.1145\/2213977.2214056"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00600-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-019-00600-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00600-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,7,9]],"date-time":"2020-07-09T23:10:49Z","timestamp":1594336249000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-019-00600-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,7,11]]},"references-count":39,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2020,1]]}},"alternative-id":["600"],"URL":"https:\/\/doi.org\/10.1007\/s00453-019-00600-w","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,7,11]]},"assertion":[{"value":"15 April 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 June 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 July 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}