{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T04:44:16Z","timestamp":1742964256548,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642280498"},{"type":"electronic","value":"9783642280504"}],"license":[{"start":{"date-parts":[[2012,1,1]],"date-time":"2012-01-01T00:00:00Z","timestamp":1325376000000},"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":[[2012]]},"DOI":"10.1007\/978-3-642-28050-4_14","type":"book-chapter","created":{"date-parts":[[2012,3,8]],"date-time":"2012-03-08T23:40:26Z","timestamp":1331250026000},"page":"169-180","source":"Crossref","is-referenced-by-count":3,"title":["Safe Approximation and Its Relation to Kernelization"],"prefix":"10.1007","author":[{"given":"Jiong","family":"Guo","sequence":"first","affiliation":[]},{"given":"Iyad","family":"Kanj","sequence":"additional","affiliation":[]},{"given":"Stefan","family":"Kratsch","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"3","key":"14_CR1","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1145\/990308.990309","volume":"51","author":"J. Alber","year":"2004","unstructured":"Alber, J., Fellows, M., Niedermeier, R.: Polynomial-time data reduction for dominating set. J. ACM\u00a051(3), 363\u2013384 (2004)","journal-title":"J. ACM"},{"issue":"3","key":"14_CR2","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1137\/S0895480196305124","volume":"12","author":"V. Bafna","year":"1999","unstructured":"Bafna, V., Berman, P., Fujito, T.: A 2-approximation algorithm for the Undirected Feedback Vertex Set problem. SIAM J. Discrete Math.\u00a012(3), 289\u2013297 (1999)","journal-title":"SIAM J. Discrete Math."},{"issue":"1","key":"14_CR3","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1145\/174644.174650","volume":"41","author":"B. Baker","year":"1994","unstructured":"Baker, B.: Approximation algorithms for NP-complete problems on planar graphs. J. ACM\u00a041(1), 153\u2013180 (1994)","journal-title":"J. ACM"},{"key":"14_CR4","first-page":"27","volume":"25","author":"R. Bar-Yehuda","year":"1985","unstructured":"Bar-Yehuda, R., Even, S.: A local-ratio theorem for approximating the Weighted Vertex Cover problem. Annals of Discrete Mathematics\u00a025, 27\u201346 (1985)","journal-title":"Annals of Discrete Mathematics"},{"issue":"4","key":"14_CR5","doi-asserted-by":"publisher","first-page":"942","DOI":"10.1137\/S0097539796305109","volume":"27","author":"R. Bar-Yehuda","year":"1998","unstructured":"Bar-Yehuda, R., Geiger, D., Naor, J., Roth, R.: Approximation algorithms for the Feedback Vertex Set problem with applications to constraint satisfaction and bayesian inference. SIAM J. Comput.\u00a027(4), 942\u2013959 (1998)","journal-title":"SIAM J. Comput."},{"key":"14_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"160","DOI":"10.1007\/978-3-540-79723-4_16","volume-title":"Parameterized and Exact Computation","author":"H.L. Bodlaender","year":"2008","unstructured":"Bodlaender, H.L., Penninkx, E.: A Linear Kernel for Planar Feedback Vertex Set. In: Grohe, M., Niedermeier, R. (eds.) IWPEC 2008. LNCS, vol.\u00a05018, pp. 160\u2013171. Springer, Heidelberg (2008)"},{"key":"14_CR7","doi-asserted-by":"publisher","first-page":"560","DOI":"10.1137\/0222038","volume":"22","author":"J. Buss","year":"1993","unstructured":"Buss, J., Goldsmith, J.: Nondeterminism within P. SIAM J. Comput.\u00a022, 560\u2013572 (1993)","journal-title":"SIAM J. Comput."},{"key":"14_CR8","doi-asserted-by":"publisher","first-page":"465","DOI":"10.1006\/jcss.1997.1490","volume":"54","author":"L. Cai","year":"1997","unstructured":"Cai, L., Chen, J.: Fixed parameter tractability and approximability of NP-hard optimization problems. J. Comput. Syst. Sci.\u00a054, 465\u2013474 (1997)","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"14_CR9","doi-asserted-by":"publisher","first-page":"459","DOI":"10.1007\/s00224-007-1346-y","volume":"41","author":"L. Cai","year":"2007","unstructured":"Cai, L., Fellows, M., Juedes, D., Rosamond, F.: The complexity of polynomial-time approximation. Theory Comput. Syst.\u00a041(3), 459\u2013477 (2007)","journal-title":"Theory Comput. Syst."},{"key":"14_CR10","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1016\/S0020-0190(97)00164-6","volume":"64","author":"M. Cesati","year":"1997","unstructured":"Cesati, M., Trevisan, L.: On the efficiency of polynomial time approximation schemes. Inf. Process. Lett.\u00a064, 165\u2013171 (1997)","journal-title":"Inf. Process. Lett."},{"issue":"4","key":"14_CR11","doi-asserted-by":"publisher","first-page":"1077","DOI":"10.1137\/050646354","volume":"37","author":"J. Chen","year":"2007","unstructured":"Chen, J., Fernau, H., Kanj, I., Xia, G.: Parametric duality and kernelization: Lower bounds and upper bounds on kernel size. SICOMP\u00a037(4), 1077\u20131106 (2007)","journal-title":"SICOMP"},{"issue":"8","key":"14_CR12","doi-asserted-by":"publisher","first-page":"1346","DOI":"10.1016\/j.jcss.2006.04.007","volume":"72","author":"J. Chen","year":"2006","unstructured":"Chen, J., Huang, X., Kanj, I., Xia, G.: Linear FPT reductions and computational lower bounds. J. Comput. Syst. Sci.\u00a072(8), 1346\u20131367 (2006)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"14_CR13","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1016\/j.dam.2006.04.040","volume":"155","author":"J. Chen","year":"2007","unstructured":"Chen, J., Huang, X., Kanj, I., Xia, G.: Polynomial time approximation schemes and parameterized complexity. Discrete Appl. Mathematics\u00a0155(2), 180\u2013193 (2007)","journal-title":"Discrete Appl. Mathematics"},{"key":"14_CR14","doi-asserted-by":"publisher","first-page":"280","DOI":"10.1006\/jagm.2001.1186","volume":"41","author":"J. Chen","year":"2001","unstructured":"Chen, J., Kanj, I., Jia, W.: Vertex cover: further observations and further improvements. J. Algorithms\u00a041, 280\u2013301 (2001)","journal-title":"J. Algorithms"},{"doi-asserted-by":"crossref","unstructured":"Dell, H., van Melkebeek, D.: Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses. In: STOC, pp. 251\u2013260 (2010)","key":"14_CR15","DOI":"10.1145\/1806689.1806725"},{"key":"14_CR16","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"R. Downey","year":"1999","unstructured":"Downey, R., Fellows, M.: Parameterized Complexity. Springer, New York (1999)"},{"key":"14_CR17","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1016\/S0022-0000(74)80044-9","volume":"9","author":"D. Johnson","year":"1974","unstructured":"Johnson, D.: Approximation algorithms for combinatorial problems. J. Comput. Syst. Sci.\u00a09, 256\u2013278 (1974)","journal-title":"J. Comput. Syst. Sci."},{"unstructured":"Kanj, I., Pelsmajer, M., Xia, G., Schaefer, M.: On the induced matching problem. In: STACS. LIPIcs, vol.\u00a008001, pp. 397\u2013408 (2008)","key":"14_CR18"},{"key":"14_CR19","doi-asserted-by":"publisher","first-page":"391","DOI":"10.1006\/jcss.1995.1031","volume":"50","author":"P. Kolaitis","year":"1995","unstructured":"Kolaitis, P., Thakur, M.: Approximation properties of NP minimization classes. J. Comput. Syst. Sci.\u00a050, 391\u2013411 (1995)","journal-title":"J. Comput. Syst. Sci."},{"unstructured":"Kratsch, S.: Polynomial kernelizations for MIN F\u2009+\u2009\u03a01 and MAX NP. In: STACS. LIPIcs, vol.\u00a03, pp. 601\u2013612 (2009)","key":"14_CR20"},{"key":"14_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"448","DOI":"10.1007\/11561071_41","volume-title":"Algorithms \u2013 ESA 2005","author":"D. Marx","year":"2005","unstructured":"Marx, D.: Efficient Approximation Schemes for Geometric Problems? In: Brodal, G.S., Leonardi, S. (eds.) ESA 2005. LNCS, vol.\u00a03669, pp. 448\u2013459. Springer, Heidelberg (2005)"},{"issue":"1","key":"14_CR22","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1093\/comjnl\/bxm048","volume":"51","author":"D. Marx","year":"2008","unstructured":"Marx, D.: Parameterized complexity and approximation algorithms. Comput. J.\u00a051(1), 60\u201378 (2008)","journal-title":"Comput. J."},{"key":"14_CR23","doi-asserted-by":"publisher","first-page":"232","DOI":"10.1007\/BF01580444","volume":"8","author":"G. Nemhauser","year":"1975","unstructured":"Nemhauser, G., Trotter, L.: Vertex packing: structural properties and algorithms. Mathematical Programming\u00a08, 232\u2013248 (1975)","journal-title":"Mathematical Programming"},{"key":"14_CR24","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"C. Papadimitriou","year":"1991","unstructured":"Papadimitriou, C., Yannakakis, M.: Optimization, approximation, and complexity classes. J. Comput. Syst. Sci.\u00a043, 425\u2013440 (1991)","journal-title":"J. Comput. Syst. Sci."},{"issue":"5","key":"14_CR25","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1016\/0020-0190(82)90022-9","volume":"14","author":"C. Savage","year":"1982","unstructured":"Savage, C.: Depth-first search and the vertex cover problem. Inf. Process. Lett.\u00a014(5), 233\u2013237 (1982)","journal-title":"Inf. Process. Lett."},{"doi-asserted-by":"crossref","unstructured":"Thomass\u00e9, S.: A 4k\n                2 kernel for feedback vertex set. ACM Transactions on Algorithms\u00a06(2) (2010)","key":"14_CR26","DOI":"10.1145\/1721837.1721848"}],"container-title":["Lecture Notes in Computer Science","Parameterized and Exact Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-28050-4_14","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,28]],"date-time":"2019-04-28T09:34:09Z","timestamp":1556444049000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-28050-4_14"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642280498","9783642280504"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-28050-4_14","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}