{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T10:42:04Z","timestamp":1742985724100,"version":"3.40.3"},"publisher-location":"Cham","reference-count":29,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319905297"},{"type":"electronic","value":"9783319905303"}],"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"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018]]},"DOI":"10.1007\/978-3-319-90530-3_17","type":"book-chapter","created":{"date-parts":[[2018,4,24]],"date-time":"2018-04-24T07:23:53Z","timestamp":1524554633000},"page":"194-206","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Conflict Free Version of Covering Problems on Graphs: Classical and Parameterized"],"prefix":"10.1007","author":[{"given":"Pallavi","family":"Jain","sequence":"first","affiliation":[]},{"given":"Lawqueen","family":"Kanesh","sequence":"additional","affiliation":[]},{"given":"Pranabendu","family":"Misra","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,4,25]]},"reference":[{"key":"17_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-662-49529-2_1","volume-title":"LATIN 2016: Theoretical Informatics","author":"A Agrawal","year":"2016","unstructured":"Agrawal, A., Kolay, S., Lokshtanov, D., Saurabh, S.: A faster FPT algorithm and a smaller kernel for Block Graph Vertex Deletion. In: Kranakis, E., Navarro, G., Ch\u00e1vez, E. (eds.) LATIN 2016. LNCS, vol. 9644, pp. 1\u201313. Springer, Heidelberg (2016). https:\/\/doi.org\/10.1007\/978-3-662-49529-2_1"},{"key":"17_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"318","DOI":"10.1007\/978-3-662-48971-0_28","volume-title":"Algorithms and Computation","author":"EM 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: Elbassioni, K., Makino, K. (eds.) ISAAC 2015. LNCS, vol. 9472, pp. 318\u2013328. Springer, Heidelberg (2015). https:\/\/doi.org\/10.1007\/978-3-662-48971-0_28"},{"unstructured":"Arkin, E.M., Banik, A., Carmi, P., Citovsky, G., Katz, M.J., Mitchell, J.S.B., Simakov, M.: Conflict-free covering. In: CCCG (2015)","key":"17_CR3"},{"unstructured":"Banik, A., Panolan, F., Raman, V., Sahlot, V.: Fr\u00e9chet distance between a line and avatar point set. In: FSTTCS, pp. 32:1\u201332:14 (2016)","key":"17_CR4"},{"issue":"4","key":"17_CR5","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1016\/0020-0190(96)00050-6","volume":"58","author":"L Cai","year":"1996","unstructured":"Cai, L.: Fixed-parameter tractability of graph modification problems for hereditary properties. Inf. Process. Lett. 58(4), 171\u2013176 (1996)","journal-title":"Inf. Process. Lett."},{"issue":"3","key":"17_CR6","doi-asserted-by":"publisher","first-page":"21:1","DOI":"10.1145\/2629595","volume":"11","author":"Y Cao","year":"2015","unstructured":"Cao, Y., Marx, D.: Interval deletion is fixed-parameter tractable. ACM Trans. Algorithms 11(3), 21:1\u201321:35 (2015)","journal-title":"ACM Trans. Algorithms"},{"issue":"40\u201342","key":"17_CR7","doi-asserted-by":"publisher","first-page":"3736","DOI":"10.1016\/j.tcs.2010.06.026","volume":"411","author":"J Chen","year":"2010","unstructured":"Chen, J., Kanj, I.A., Xia, G.: Improved upper bounds for vertex cover. Theor. Comput. Sci. 411(40\u201342), 3736\u20133756 (2010)","journal-title":"Theor. Comput. Sci."},{"key":"17_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, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-21275-3"},{"key":"17_CR9","series-title":"Lecture Notes in Computer Science (Lecture Notes in Artificial Intelligence)","doi-asserted-by":"publisher","first-page":"414","DOI":"10.1007\/978-3-642-04428-1_36","volume-title":"Algorithmic Decision Theory","author":"A Darmann","year":"2009","unstructured":"Darmann, A., Pferschy, U., Schauer, J.: Determining a minimum spanning tree with disjunctive constraints. In: Rossi, F., Tsoukias, A. (eds.) ADT 2009. LNCS (LNAI), vol. 5783, pp. 414\u2013423. Springer, Heidelberg (2009). https:\/\/doi.org\/10.1007\/978-3-642-04428-1_36"},{"issue":"16","key":"17_CR10","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."},{"issue":"2","key":"17_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":"17_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. J. Sched. 12(2), 199\u2013224 (2009)","journal-title":"J. Sched."},{"doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Lokshtanov, D., Misra, N., Saurabh, S.: Planar F-deletion: approximation, kernelization and optimal FPT algorithms. In: FOCS (2012)","key":"17_CR13","DOI":"10.1109\/FOCS.2012.62"},{"key":"17_CR14","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1016\/S0166-218X(98)00035-3","volume":"86","author":"T Fujito","year":"1998","unstructured":"Fujito, T.: A unified approximation algorithm for node-deletion problems. Discret. Appl. Math. 86, 213\u2013231 (1998)","journal-title":"Discret. Appl. Math."},{"issue":"2","key":"17_CR15","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1007\/BF01758838","volume":"8","author":"D Gusfield","year":"1992","unstructured":"Gusfield, D., Pitt, L.: A bounded approximation for the minimum cost 2-sat problem. Algorithmica 8(2), 103\u2013117 (1992)","journal-title":"Algorithmica"},{"key":"17_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"52","DOI":"10.1007\/3-540-56939-1_61","volume-title":"Automata, Languages and Programming","author":"V Kann","year":"1993","unstructured":"Kann, V.: Polynomially bounded minimization problems which are hard to approximate. In: Lingas, A., Karlsson, R., Carlsson, S. (eds.) ICALP 1993. LNCS, vol. 700, pp. 52\u201363. Springer, Heidelberg (1993). https:\/\/doi.org\/10.1007\/3-540-56939-1_61"},{"issue":"10","key":"17_CR17","doi-asserted-by":"publisher","first-page":"556","DOI":"10.1016\/j.ipl.2014.05.001","volume":"114","author":"T Kociumaka","year":"2014","unstructured":"Kociumaka, T., Pilipczuk, M.: Faster deterministic feedback vertex set. Inf. Process. Lett. 114(10), 556\u2013560 (2014)","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"17_CR18","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1016\/0022-0000(80)90060-4","volume":"20","author":"JM Lewis","year":"1980","unstructured":"Lewis, J.M., Yannakakis, M.: The node-deletion problem for hereditary properties is NP-complete. J. Comput. Syst. Sci. 20(2), 219\u2013230 (1980)","journal-title":"J. Comput. Syst. Sci."},{"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. CoRR abs\/1705.01414 (to appear in SODA 2018)","key":"17_CR19","DOI":"10.1137\/1.9781611975031.177"},{"key":"17_CR20","doi-asserted-by":"publisher","first-page":"960","DOI":"10.1145\/185675.306789","volume":"41","author":"C Lund","year":"1994","unstructured":"Lund, C., Yannakakis, M.: On the hardness of approximating minimization problems. J. ACM 41, 960\u2013981 (1994)","journal-title":"J. ACM"},{"issue":"4","key":"17_CR21","doi-asserted-by":"publisher","first-page":"747","DOI":"10.1007\/s00453-008-9233-8","volume":"57","author":"D Marx","year":"2010","unstructured":"Marx, D.: Chordal deletion is fixed-parameter tractable. Algorithmica 57(4), 747\u2013768 (2010)","journal-title":"Algorithmica"},{"key":"17_CR22","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1016\/j.tcs.2013.07.019","volume":"506","author":"N Misra","year":"2013","unstructured":"Misra, N., Narayanaswamy, N.S., Raman, V., Shankar, B.S.: Solving min ones 2-sat as fast as vertex cover. Theor. Comput. Sci. 506, 115\u2013121 (2013)","journal-title":"Theor. Comput. Sci."},{"key":"17_CR23","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1016\/j.tcs.2012.02.012","volume":"461","author":"N Misra","year":"2012","unstructured":"Misra, N., Philip, G., Raman, V., Saurabh, S.: On parameterized independent feedback vertex set. Theor. Comput. Sci. 461, 65\u201375 (2012)","journal-title":"Theor. Comput. Sci."},{"key":"17_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1007\/978-3-642-21527-8_34","volume-title":"Network Optimization","author":"U Pferschy","year":"2011","unstructured":"Pferschy, U., Schauer, J.: The maximum flow problem with conflict and forcing conditions. In: Pahl, J., Reiners, T., Vo\u00df, S. (eds.) INOC 2011. LNCS, vol. 6701, pp. 289\u2013294. Springer, Heidelberg (2011). https:\/\/doi.org\/10.1007\/978-3-642-21527-8_34"},{"issue":"1","key":"17_CR25","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1007\/s10878-011-9438-7","volume":"26","author":"U Pferschy","year":"2013","unstructured":"Pferschy, U., Schauer, J.: The maximum flow problem with disjunctive constraints. J. Comb. Optim. 26(1), 109\u2013119 (2013)","journal-title":"J. Comb. Optim."},{"issue":"4","key":"17_CR26","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":"4","key":"17_CR27","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1016\/j.orl.2003.10.009","volume":"32","author":"BA Reed","year":"2004","unstructured":"Reed, B.A., Smith, K., Vetta, A.: Finding odd cycle transversals. Oper. Res. Lett. 32(4), 299\u2013301 (2004)","journal-title":"Oper. Res. Lett."},{"key":"17_CR28","doi-asserted-by":"publisher","first-page":"126","DOI":"10.1016\/j.ic.2017.06.001","volume":"255","author":"M Xiao","year":"2017","unstructured":"Xiao, M., Nagamochi, H.: Exact algorithms for maximum independent set. Inf. Comput. 255, 126\u2013146 (2017)","journal-title":"Inf. Comput."},{"doi-asserted-by":"crossref","unstructured":"Yannakakis, M.: Node-and edge-deletion NP-complete problems. In: STOC, pp. 253\u2013264. ACM, New York (1978)","key":"17_CR29","DOI":"10.1145\/800133.804355"}],"container-title":["Lecture Notes in Computer Science","Computer Science \u2013 Theory and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-90530-3_17","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,12]],"date-time":"2024-03-12T11:30:26Z","timestamp":1710243026000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-90530-3_17"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783319905297","9783319905303"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-90530-3_17","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":"25 April 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CSR","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Computer Science Symposium in Russia","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Moscow","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Russia","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":"6 June 2018","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"10 June 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":"csr2018","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/logic.pdmi.ras.ru\/csr2018\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}