{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T13:48:31Z","timestamp":1725889711889},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2021,1,12]],"date-time":"2021-01-12T00:00:00Z","timestamp":1610409600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,1,12]],"date-time":"2021-01-12T00:00:00Z","timestamp":1610409600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2021,4]]},"DOI":"10.1007\/s00224-020-10022-9","type":"journal-article","created":{"date-parts":[[2021,1,13]],"date-time":"2021-01-13T03:31:44Z","timestamp":1610508704000},"page":"515-540","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Parameterized Complexity of Conflict-Free Set Cover"],"prefix":"10.1007","volume":"65","author":[{"given":"Ashwin","family":"Jacob","sequence":"first","affiliation":[]},{"given":"Diptapriyo","family":"Majumdar","sequence":"additional","affiliation":[]},{"given":"Venkatesh","family":"Raman","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,1,12]]},"reference":[{"key":"10022_CR1","unstructured":"Agrawal, A., Jain, P., Kanesh, L., Lokshtanov, D., Saurabh, S.: Conflict free feedback vertex set: a parameterized dichotomy. In: 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2018)"},{"key":"10022_CR2","doi-asserted-by":"crossref","unstructured":"Arkin, E.M., Banik, A., Carmi, P., Citovsky, G., Katz, M.J., Mitchell, J.S., Simakov, M.: Choice is hard. In: International Symposium on Algorithms and Computation, pp 318\u2013328. Springer (2015)","DOI":"10.1007\/978-3-662-48971-0_28"},{"key":"10022_CR3","unstructured":"Arkin, E.M., Banik, A., Carmi, P., Citovsky, G., Katz, M.J., Mitchell, J.S., Simakov, M.: Conflict-free covering. In: Conference on Computational Geometry, p 17 (2015)"},{"issue":"3","key":"10022_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: An International Journal 36(3), 147\u2013155 (2000)","journal-title":"Networks: An International Journal"},{"issue":"9","key":"10022_CR5","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)","journal-title":"Algorithmica"},{"issue":"1","key":"10022_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00453-019-00600-w","volume":"82","author":"A Banik","year":"2020","unstructured":"Banik, A., Panolan, F., Raman, V., Sahlot, V., Saurabh, S.: Parameterized complexity of geometric covering problems having conflicts. Algorithmica 82(1), 1\u201319 (2020)","journal-title":"Algorithmica"},{"issue":"3","key":"10022_CR7","first-page":"41","volume":"12","author":"M Cygan","year":"2016","unstructured":"Cygan, M., Dell, H., Lokshtanov, D., Marx, D., Nederlof, J., Okamoto, Y., Paturi, R., Saurabh, S., Wahlstr\u00f6m, M.: On problems as hard as CNF-SAT. ACM Transactions on Algorithms (TALG) 12(3), 41 (2016)","journal-title":"ACM Transactions on Algorithms (TALG)"},{"key":"10022_CR8","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. Springer, Berlin (2015)"},{"issue":"16","key":"10022_CR9","doi-asserted-by":"publisher","first-page":"1726","DOI":"10.1016\/j.dam.2010.12.016","volume":"159","author":"A Darmann","year":"2011","unstructured":"Darmann, A., Pferschy, U., Schauer, J., Woeginger, G.J.: Paths, trees and matchings under disjunctive constraints. Discret. Appl. Math. 159 (16), 1726\u20131735 (2011)","journal-title":"Discret. Appl. Math."},{"key":"10022_CR10","volume-title":"Graph Theory","author":"R Diestel","year":"2006","unstructured":"Diestel, R.: Graph Theory. Springer, Berlin (2006)"},{"issue":"2","key":"10022_CR11","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1016\/j.disopt.2010.11.001","volume":"8","author":"L Epstein","year":"2011","unstructured":"Epstein, L., Favrholdt, L.M., Levin, A.: Online variable-sized bin packing with conflicts. Discret. Optim. 8(2), 333\u2013343 (2011)","journal-title":"Discret. Optim."},{"issue":"2","key":"10022_CR12","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1007\/s10951-008-0089-1","volume":"12","author":"G Even","year":"2009","unstructured":"Even, G., Halld\u00f3rsson, M.M., Kaplan, L., Ron, D.: Scheduling with conflicts: online and offline algorithms. Journal of Scheduling 12(2), 199\u2013224 (2009)","journal-title":"Journal of Scheduling"},{"issue":"3","key":"10022_CR13","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1016\/0012-365X(89)90268-9","volume":"73","author":"M Farber","year":"1989","unstructured":"Farber, M.: On diameters and radii of bridged graphs. Discret. Math. 73(3), 249\u2013260 (1989)","journal-title":"Discret. Math."},{"key":"10022_CR14","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Kratsch, D., Woeginger, G.J.: Exact (exponential) algorithms for the dominating set problem. In: International Workshop on Graph-Theoretic Concepts in Computer Science, pp 245\u2013256. Springer (2004)","DOI":"10.1007\/978-3-540-30559-0_21"},{"issue":"4","key":"10022_CR15","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. Journal of the ACM (JACM) 63(4), 29 (2016)","journal-title":"Journal of the ACM (JACM)"},{"key":"10022_CR16","doi-asserted-by":"crossref","unstructured":"Golumbic, M.C: Algorithmic graph theory and perfect graphs. Annals of Discrete Mathematics 57 (2004)","DOI":"10.1016\/S0167-5060(04)80059-1"},{"issue":"4","key":"10022_CR17","doi-asserted-by":"publisher","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? Journal of Computer and System Sciences (JCSS) 63(4), 512\u2013530 (2001)","journal-title":"Journal of Computer and System Sciences (JCSS)"},{"key":"10022_CR18","doi-asserted-by":"crossref","unstructured":"Jacob, A., Majumdar, D., Raman, V.: Parameterized complexity of conflict-free set cover. In: International Computer Science Symposium in Russia, pp 191\u2013202. Springer (2019)","DOI":"10.1007\/978-3-030-19955-5_17"},{"issue":"6","key":"10022_CR19","doi-asserted-by":"publisher","first-page":"1067","DOI":"10.1007\/s00224-019-09964-6","volume":"64","author":"P Jain","year":"2020","unstructured":"Jain, P., Kanesh, L., Misra, P.: Conflict Free Version of Covering Problems on Graphs: Classical and Parameterized. Theory Comput. Syst. 64(6), 1067\u20131093 (2020). https:\/\/doi.org\/10.1007\/s00224-019-09964-6","journal-title":"Theory Comput. Syst."},{"issue":"3","key":"10022_CR20","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1016\/0020-0190(88)90065-8","volume":"27","author":"DS Johnson","year":"1988","unstructured":"Johnson, D.S., Yannakakis, M., Papadimitriou, C.H.: On generating all maximal independent sets. Inf. Process. Lett. 27(3), 119\u2013123 (1988)","journal-title":"Inf. Process. Lett."},{"key":"10022_CR21","doi-asserted-by":"crossref","unstructured":"Kann, V.: Polynomially bounded minimization problems which are hard to approximate. In: International Colloquium on Automata, Languages, and Programming, pp 52\u201363. Springer (1993)","DOI":"10.1007\/3-540-56939-1_61"},{"key":"10022_CR22","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0045375","volume-title":"Treewidth: Computations and Approximations, vol. 842","author":"T Kloks","year":"1994","unstructured":"Kloks, T.: Treewidth: Computations and Approximations, vol. 842. Springer Science & Business Media, Berlin (1994)"},{"key":"10022_CR23","doi-asserted-by":"crossref","unstructured":"Kumar, V.S.A., Arya, S., Ramesh, H.: Hardness of set cover with intersection 1. In: Rolim, J.D.P., Welzl, E. (eds.) Automata, Languages and Programming, pp 624\u2013635. Springer, Berlin (2000)","DOI":"10.1007\/3-540-45022-X_53"},{"issue":"3","key":"10022_CR24","doi-asserted-by":"publisher","first-page":"675","DOI":"10.1137\/16M1104834","volume":"47","author":"D Lokshtanov","year":"2018","unstructured":"Lokshtanov, D., Marx, D., Saurabh, S.: Slightly superexponential parameterized problems. SIAM J. Comput. 47(3), 675\u2013702 (2018)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"10022_CR25","first-page":"14","volume":"14","author":"D Lokshtanov","year":"2018","unstructured":"Lokshtanov, D., Misra, P., Panolan, F., Saurabh, S.: Deterministic truncation of linear matroids. ACM Transactions on Algorithms (TALG) 14(2), 14 (2018)","journal-title":"ACM Transactions on Algorithms (TALG)"},{"key":"10022_CR26","doi-asserted-by":"crossref","unstructured":"Lokshtanov, D., Panolan, F., Saurabh, S., Sharma, R., Zehavi, M.: Covering small independent sets and separators with applications to parameterized algorithms. In: Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pp 2785\u20132800. Society for Industrial and Applied Mathematics (2018)","DOI":"10.1137\/1.9781611975031.177"},{"issue":"44","key":"10022_CR27","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":"10022_CR28","unstructured":"Marx, D., Salmasi, A., Sidiropoulos, A.: Constant-factor approximations for asymmetric TSP on nearly-embeddable graphs. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX\/RANDOM 2016, vol. 60 of LIPIcs, pp 16:1\u201316:54. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2016)"},{"issue":"4","key":"10022_CR29","doi-asserted-by":"publisher","first-page":"600","DOI":"10.1016\/j.ejc.2011.01.006","volume":"32","author":"J Ne\u0161et\u0159il","year":"2011","unstructured":"Ne\u0161et\u0159il, J., De Mendez, P.O.: On nowhere dense graphs. Eur. J. Comb. 32(4), 600\u2013617 (2011)","journal-title":"Eur. J. Comb."},{"key":"10022_CR30","volume-title":"Matroid Theory, vol. 3","author":"JG Oxley","year":"2006","unstructured":"Oxley, J.G.: Matroid Theory, vol. 3. Oxford University Press, USA (2006)"},{"key":"10022_CR31","doi-asserted-by":"crossref","unstructured":"Pferschy, U., Schauer, J.: The maximum flow problem with conflict and forcing conditions. In: Network Optimization, pp 289\u2013294. Springer (2011)","DOI":"10.1007\/978-3-642-21527-8_34"},{"issue":"4","key":"10022_CR32","doi-asserted-by":"publisher","first-page":"1300","DOI":"10.1007\/s10878-016-0035-7","volume":"33","author":"U Pferschy","year":"2017","unstructured":"Pferschy, U., Schauer, J.: Approximation of knapsack problems with conflict and forcing graphs. J. Comb. Optim. 33(4), 1300\u20131323 (2017)","journal-title":"J. Comb. Optim."},{"issue":"2","key":"10022_CR33","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":"10022_CR34","doi-asserted-by":"crossref","unstructured":"van Bevern, R., Tsidulko, O.Y., Zschoche, P.: Fixed-parameter algorithms for maximum-profit facility location under matroid constraints. In: International Conference on Algorithms and Complexity, pp 62\u201374. Springer (2019)","DOI":"10.1007\/978-3-030-17402-6_6"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-020-10022-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-020-10022-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-020-10022-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,21]],"date-time":"2021-05-21T08:04:59Z","timestamp":1621584299000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-020-10022-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1,12]]},"references-count":34,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,4]]}},"alternative-id":["10022"],"URL":"https:\/\/doi.org\/10.1007\/s00224-020-10022-9","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,1,12]]},"assertion":[{"value":"20 November 2020","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 January 2021","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}