{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T05:15:55Z","timestamp":1743052555820,"version":"3.40.3"},"publisher-location":"Cham","reference-count":40,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319751719"},{"type":"electronic","value":"9783319751726"}],"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-75172-6_4","type":"book-chapter","created":{"date-parts":[[2018,1,30]],"date-time":"2018-01-30T11:23:02Z","timestamp":1517311382000},"page":"32-43","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Approximating Partially Bounded Degree Deletion on Directed Graphs"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7892-6426","authenticated-orcid":false,"given":"Toshihiro","family":"Fujito","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kei","family":"Kimura","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yuki","family":"Mizuno","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,1,31]]},"reference":[{"issue":"1","key":"4_CR1","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1287\/opre.1100.0851","volume":"59","author":"B Balasundaram","year":"2011","unstructured":"Balasundaram, B., Butenko, S., Hicks, I.V.: Clique relaxations in social network analysis: the maximum $$k$$-plex problem. Oper. Res. 59(1), 133\u2013142 (2011)","journal-title":"Oper. Res."},{"issue":"2","key":"4_CR2","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1006\/jagm.2000.1150","volume":"39","author":"R Bar-Yehuda","year":"2001","unstructured":"Bar-Yehuda, R.: Using homogeneous weights for approximating the partial cover problem. J. Algorithms 39(2), 137\u2013144 (2001)","journal-title":"J. Algorithms"},{"issue":"1\u20132","key":"4_CR3","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/j.dam.2011.08.013","volume":"160","author":"N Betzler","year":"2012","unstructured":"Betzler, N., Bredereck, R., Niedermeier, R., Uhlmann, J.: On bounded-degree vertex deletion parameterized by treewidth. Discret. Appl. Math. 160(1\u20132), 53\u201360 (2012)","journal-title":"Discret. Appl. Math."},{"key":"4_CR4","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1016\/j.dam.2014.05.042","volume":"177","author":"B Bre\u0161ar","year":"2014","unstructured":"Bre\u0161ar, B., Krivo\u0161-Bellu\u0161, R., Semani\u0161in, G., \u0160parl, P.: On the weighted $$k$$-path vertex cover problem. Discret. Appl. Math. 177, 14\u201318 (2014)","journal-title":"Discret. Appl. Math."},{"issue":"13\u201314","key":"4_CR5","doi-asserted-by":"crossref","first-page":"1943","DOI":"10.1016\/j.dam.2013.02.024","volume":"161","author":"B Bre\u0161ar","year":"2013","unstructured":"Bre\u0161ar, B., Jakovac, M., Katreni\u010d, J., Semani\u0161in, G., Taranenko, A.: On the vertex $$k$$-path cover. Discret. Appl. Math. 161(13\u201314), 1943\u20131949 (2013)","journal-title":"Discret. Appl. Math."},{"issue":"12","key":"4_CR6","doi-asserted-by":"publisher","first-page":"1189","DOI":"10.1016\/j.dam.2011.04.008","volume":"159","author":"B Bre\u0161ar","year":"2011","unstructured":"Bre\u0161ar, B., Kardo\u0161, F., Katreni\u010d, J., Semani\u0161in, G.: Minimum $$k$$-path vertex cover. Discret. Appl. Math. 159(12), 1189\u20131195 (2011)","journal-title":"Discret. Appl. Math."},{"key":"4_CR7","unstructured":"Camby, E., Cardinal, J., Chapelle, M., Fiorini, S., Joret, G.: A primal-dual 3-approximation algorithm for hitting 4-vertex paths. In: 9th International Colloquium on Graph Theory and Combinatorics, ICGT 2014, p. 61 (2014)"},{"key":"4_CR8","unstructured":"Case, B.M., Hedetniemi, S.T., Laskar, R.C., Lipman, D.J.: Partial domination in graphs. arXiv e-prints (2017)"},{"issue":"11","key":"4_CR9","doi-asserted-by":"publisher","first-page":"e1000234","DOI":"10.1371\/journal.pcbi.1000234","volume":"4","author":"C Chauve","year":"2008","unstructured":"Chauve, C., Tannier, E.: A methodological framework for the reconstruction of contiguous regions of ancestral genomes and its application to mammalian genomes. PLoS Comput. Biol. 4(11), e1000234 (2008)","journal-title":"PLoS Comput. Biol."},{"key":"4_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"90","DOI":"10.1007\/978-3-642-14355-7_10","volume-title":"Algorithmic Aspects in Information and Management","author":"Z-Z Chen","year":"2010","unstructured":"Chen, Z.-Z., Fellows, M., Fu, B., Jiang, H., Liu, Y., Wang, L., Zhu, B.: A linear kernel for co-path\/cycle packing. In: Chen, B. (ed.) AAIM 2010. LNCS, vol. 6124, pp. 90\u2013102. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-14355-7_10"},{"key":"4_CR11","unstructured":"Das, A.: Partial domination in graphs. arXiv e-prints (2017)"},{"issue":"5","key":"4_CR12","doi-asserted-by":"publisher","first-page":"1129","DOI":"10.1137\/S0097539704443057","volume":"34","author":"I Dinur","year":"2005","unstructured":"Dinur, I., Guruswami, V., Khot, S., Regev, O.: A new multilayered PCP and the hardness of hypergraph vertex cover. SIAM J. Comput. 34(5), 1129\u20131146 (2005)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"4_CR13","doi-asserted-by":"publisher","first-page":"439","DOI":"10.4007\/annals.2005.162.439","volume":"162","author":"I Dinur","year":"2005","unstructured":"Dinur, I., Safra, S.: On the hardness of approximating minimum vertex cover. Ann. Math. (2) 162(1), 439\u2013485 (2005)","journal-title":"Ann. Math. (2)"},{"key":"4_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"102","DOI":"10.1007\/978-3-642-12476-1_7","volume-title":"Algorithms and Applications","author":"T Elomaa","year":"2010","unstructured":"Elomaa, T., Kujala, J.: Covering analysis of the greedy algorithm for partial cover. In: Elomaa, T., Mannila, H., Orponen, P. (eds.) Algorithms and Applications. LNCS, vol. 6060, pp. 102\u2013113. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-12476-1_7"},{"issue":"6","key":"4_CR15","doi-asserted-by":"publisher","first-page":"1141","DOI":"10.1016\/j.jcss.2010.12.001","volume":"77","author":"MR Fellows","year":"2011","unstructured":"Fellows, M.R., Guo, J., Moser, H., Niedermeier, R.: A generalization of Nemhauser and Trotter\u2019s local optimization theorem. J. Comput. Syst. Sci. 77(6), 1141\u20131158 (2011)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"4_CR16","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1007\/s10878-013-9691-z","volume":"29","author":"Q Feng","year":"2015","unstructured":"Feng, Q., Wang, J., Li, S., Chen, J.: Randomized parameterized algorithms for $$P_2$$-packing and co-path packing problems. J. Comb. Optim. 29(1), 125\u2013140 (2015)","journal-title":"J. Comb. Optim."},{"issue":"2\u20133","key":"4_CR17","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(2\u20133), 213\u2013231 (1998)","journal-title":"Discret. Appl. Math."},{"issue":"4","key":"4_CR18","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1016\/S0167-6377(99)00045-0","volume":"25","author":"T Fujito","year":"1999","unstructured":"Fujito, T.: On approximation of the submodular set cover problem. Oper. Res. Lett. 25(4), 169\u2013174 (1999)","journal-title":"Oper. Res. Lett."},{"key":"4_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"234","DOI":"10.1007\/978-3-319-57586-5_20","volume-title":"Algorithms and Complexity","author":"T Fujito","year":"2017","unstructured":"Fujito, T.: Approximating bounded degree deletion via matroid matching. In: Fotakis, D., Pagourtzis, A., Paschos, V.T. (eds.) CIAC 2017. LNCS, vol. 10236, pp. 234\u2013246. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-57586-5_20"},{"issue":"1","key":"4_CR20","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1016\/j.jalgor.2004.04.002","volume":"53","author":"R Gandhi","year":"2004","unstructured":"Gandhi, R., Khuller, S., Srinivasan, A.: Approximation algorithms for partial covering problems. J. Algorithms 53(1), 55\u201384 (2004)","journal-title":"J. Algorithms"},{"key":"4_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1007\/3-540-45753-4_15","volume-title":"Approximation Algorithms for Combinatorial Optimization","author":"E Halperin","year":"2002","unstructured":"Halperin, E., Srinivasan, A.: Improved approximation algorithms for the partial vertex cover problem. In: Jansen, K., Leonardi, S., Vazirani, V. (eds.) APPROX 2002. LNCS, vol. 2462, pp. 161\u2013174. Springer, Heidelberg (2002). https:\/\/doi.org\/10.1007\/3-540-45753-4_15"},{"issue":"1","key":"4_CR22","doi-asserted-by":"publisher","first-page":"94","DOI":"10.1016\/j.disc.2012.09.010","volume":"313","author":"M Jakovac","year":"2013","unstructured":"Jakovac, M., Taranenko, A.: On the $$k$$-path vertex cover of some graph products. Discret. Math. 313(1), 94\u2013100 (2013)","journal-title":"Discret. Math."},{"key":"4_CR23","doi-asserted-by":"crossref","unstructured":"Karakostas, G.: A better approximation ratio for the vertex cover problem. ACM Trans. Algorithms 5(4), art. no. 41 (2009)","DOI":"10.1145\/1597036.1597045"},{"issue":"50","key":"4_CR24","doi-asserted-by":"publisher","first-page":"7009","DOI":"10.1016\/j.tcs.2011.09.009","volume":"412","author":"F Kardo\u0161","year":"2011","unstructured":"Kardo\u0161, F., Katreni\u010d, J., Schiermeyer, I.: On computing the minimum 3-path vertex cover and dissociation number of graphs. Theoret. Comput. Sci. 412(50), 7009\u20137017 (2011)","journal-title":"Theoret. Comput. Sci."},{"issue":"3","key":"4_CR25","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1016\/j.jcss.2007.06.019","volume":"74","author":"S Khot","year":"2008","unstructured":"Khot, S., Regev, O.: Vertex cover might be hard to approximate to within $$2-\\epsilon $$. J. Comput. Syst. Sci. 74(3), 335\u2013349 (2008)","journal-title":"J. Comput. Syst. Sci."},{"key":"4_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1007\/978-3-540-69507-3_31","volume-title":"SOFSEM 2007: Theory and Practice of Computer Science","author":"J Kneis","year":"2007","unstructured":"Kneis, J., M\u00f6lle, D., Rossmanith, P.: Partial vs. complete domination: t-dominating set. In: van Leeuwen, J., Italiano, G.F., van der Hoek, W., Meinel, C., Sack, H., Pl\u00e1\u0161il, F. (eds.) SOFSEM 2007. LNCS, vol. 4362, pp. 367\u2013376. Springer, Heidelberg (2007). https:\/\/doi.org\/10.1007\/978-3-540-69507-3_31"},{"key":"4_CR27","doi-asserted-by":"crossref","unstructured":"Lee, E.: Partitioning a graph into small pieces with applications to path transversal. In: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, pp. 1546\u20131558 (2017)","DOI":"10.1137\/1.9781611974782.101"},{"issue":"3","key":"4_CR28","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1007\/s10878-011-9391-5","volume":"24","author":"H Moser","year":"2012","unstructured":"Moser, H., Niedermeier, R., Sorge, M.J.: Exact combinatorial algorithms and experiments for finding maximum $$k$$-plexes. J. Comb. Optim. 24(3), 347\u2013373 (2012)","journal-title":"J. Comb. Optim."},{"issue":"3","key":"4_CR29","doi-asserted-by":"publisher","first-page":"1095","DOI":"10.1137\/120890946","volume":"42","author":"I Newman","year":"2013","unstructured":"Newman, I., Sohler, C.: Every property of hyperfinite graphs is testable. SIAM J. Comput. 42(3), 1095\u20131112 (2013)","journal-title":"SIAM J. Comput."},{"issue":"5","key":"4_CR30","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1016\/j.ipl.2003.08.005","volume":"88","author":"M Okun","year":"2003","unstructured":"Okun, M., Barak, A.: A new approach for approximating node deletion problems. Inform. Process. Lett. 88(5), 231\u2013236 (2003)","journal-title":"Inform. Process. Lett."},{"issue":"13","key":"4_CR31","doi-asserted-by":"publisher","first-page":"1352","DOI":"10.1016\/j.dam.2011.04.023","volume":"159","author":"Y Orlovich","year":"2011","unstructured":"Orlovich, Y., Dolgui, A., Finke, G., Gordon, V., Werner, F.: The complexity of dissociation set problems in graphs. Discret. Appl. Math. 159(13), 1352\u20131366 (2011)","journal-title":"Discret. Appl. Math."},{"issue":"1","key":"4_CR32","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1080\/0022250X.1978.9989883","volume":"6","author":"SB Seidman","year":"1978","unstructured":"Seidman, S.B., Foster, B.L.: A graph-theoretic generalization of the clique concept. J. Math. Soc. 6(1), 139\u2013154 (1978)","journal-title":"J. Math. Soc."},{"issue":"5","key":"4_CR33","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1016\/S0020-0190(97)00182-8","volume":"64","author":"P Slav\u00edk","year":"1997","unstructured":"Slav\u00edk, P.: Improved performance of the greedy algorithm for partial cover. Inform. Process. Lett. 64(5), 251\u2013254 (1997)","journal-title":"Inform. Process. Lett."},{"issue":"2","key":"4_CR34","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1016\/j.ipl.2014.06.018","volume":"115","author":"J Tu","year":"2015","unstructured":"Tu, J.: A fixed-parameter algorithm for the vertex cover $$P_3$$ problem. Inform. Process. Lett. 115(2), 96\u201399 (2015)","journal-title":"Inform. Process. Lett."},{"issue":"13","key":"4_CR35","doi-asserted-by":"publisher","first-page":"481","DOI":"10.1016\/j.ipl.2013.04.002","volume":"113","author":"J Tu","year":"2013","unstructured":"Tu, J., Yang, F.: The vertex cover $$P_3$$ problem in cubic graphs. Inform. Process. Lett. 113(13), 481\u2013485 (2013)","journal-title":"Inform. Process. Lett."},{"issue":"14","key":"4_CR36","doi-asserted-by":"publisher","first-page":"683","DOI":"10.1016\/j.ipl.2011.04.009","volume":"111","author":"J Tu","year":"2011","unstructured":"Tu, J., Zhou, W.: A factor 2 approximation algorithm for the vertex cover $$P_3$$ problem. Inform. Process. Lett. 111(14), 683\u2013686 (2011)","journal-title":"Inform. Process. Lett."},{"issue":"50","key":"4_CR37","doi-asserted-by":"publisher","first-page":"7044","DOI":"10.1016\/j.tcs.2011.09.013","volume":"412","author":"J Tu","year":"2011","unstructured":"Tu, J., Zhou, W.: A primal-dual approximation algorithm for the vertex cover $$P_3$$ problem. Theoret. Comput. Sci. 412(50), 7044\u20137048 (2011)","journal-title":"Theoret. Comput. Sci."},{"issue":"4","key":"4_CR38","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1007\/BF02579435","volume":"2","author":"LA Wolsey","year":"1982","unstructured":"Wolsey, L.A.: An analysis of the greedy algorithm for the submodular set covering problem. Combinatorica 2(4), 385\u2013393 (1982)","journal-title":"Combinatorica"},{"key":"4_CR39","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1016\/j.jcss.2016.08.003","volume":"84","author":"M Xiao","year":"2017","unstructured":"Xiao, M.: On a generalization of Nemhauser and Trotter\u2019s local optimization theorem. J. Comput. Syst. Sci. 84, 97\u2013106 (2017)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"4_CR40","doi-asserted-by":"publisher","first-page":"310","DOI":"10.1137\/0210022","volume":"10","author":"M Yannakakis","year":"1981","unstructured":"Yannakakis, M.: Node-deletion problems on bipartite graphs. SIAM J. Comput. 10(2), 310\u2013327 (1981)","journal-title":"SIAM J. Comput."}],"container-title":["Lecture Notes in Computer Science","WALCOM: Algorithms and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-75172-6_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,13]],"date-time":"2024-03-13T15:39:23Z","timestamp":1710344363000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-75172-6_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783319751719","9783319751726"],"references-count":40,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-75172-6_4","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":"31 January 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"WALCOM","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Workshop on Algorithms and Computation","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Dhaka","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Bangladesh","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":"3 March 2018","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"5 March 2018","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"12","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"walcom2018","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/cse.buet.ac.bd\/walcom2018\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}