{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T00:58:51Z","timestamp":1742950731138,"version":"3.40.3"},"publisher-location":"Cham","reference-count":31,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030261757"},{"type":"electronic","value":"9783030261764"}],"license":[{"start":{"date-parts":[[2019,1,1]],"date-time":"2019-01-01T00:00:00Z","timestamp":1546300800000},"content-version":"tdm","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":[[2019]]},"DOI":"10.1007\/978-3-030-26176-4_31","type":"book-chapter","created":{"date-parts":[[2019,7,23]],"date-time":"2019-07-23T23:02:56Z","timestamp":1563922976000},"page":"375-386","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A Simple Local Search Gives a PTAS for the Feedback Vertex Set Problem in Minor-Free Graphs"],"prefix":"10.1007","author":[{"given":"Hung","family":"Le","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Baigong","family":"Zheng","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,7,21]]},"reference":[{"issue":"4","key":"31_CR1","doi-asserted-by":"publisher","first-page":"801","DOI":"10.1090\/S0894-0347-1990-1065053-0","volume":"3","author":"N Alon","year":"1990","unstructured":"Alon, N., Seymour, P.D., Thomas, R.: A separator theorem for nonplanar graphs. J. Am. Math. Soc. 3(4), 801\u2013808 (1990)","journal-title":"J. Am. Math. Soc."},{"key":"31_CR2","unstructured":"Antunes, D., Mathieu, C., Mustafa, N.H.: Combinatorics of local search: an optimal 4-local Hall\u2019s theorem for planar graphs. In: 25th Annual European Symposium on Algorithms (ESA 2017), vol. 87, pp. 8:1\u20138:13 (2017)"},{"issue":"3","key":"31_CR3","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. 12(3), 289\u2013297 (1999)","journal-title":"SIAM J. Discrete Math."},{"issue":"1","key":"31_CR4","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1016\/0004-3702(95)00004-6","volume":"83","author":"A Becker","year":"1996","unstructured":"Becker, A., Geiger, D.: Optimization of Pearl\u2019s method of conditioning and greedy-like approximation algorithms for the vertex feedback set problem. Artif. Intell. 83(1), 167\u2013188 (1996)","journal-title":"Artif. Intell."},{"issue":"C","key":"31_CR5","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1016\/j.dam.2015.03.004","volume":"189","author":"S Cabello","year":"2015","unstructured":"Cabello, S., Gajser, D.: Simple PTAS\u2019s for families of graphs excluding a minor. Discrete Appl. Math. 189(C), 41\u201348 (2015)","journal-title":"Discrete Appl. Math."},{"key":"31_CR6","doi-asserted-by":"crossref","unstructured":"Chan, T.M., Har-Peled, S.: Approximation algorithms for maximum independent set of pseudo-disks. In: Proceedings of the Twenty-Fifth Annual Symposium on Computational Geometry, SocG 2009, pp. 333\u2013340 (2009)","DOI":"10.1145\/1542362.1542420"},{"key":"31_CR7","doi-asserted-by":"crossref","unstructured":"Cohen-Addad, V., Klein, P.N., Mathieu, C.: Local search yields approximation schemes for $$k$$-means and $$k$$-median in Euclidean and minor-free metrics. In: Proceedings of the 57th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2016 (2016)","DOI":"10.1109\/FOCS.2016.46"},{"key":"31_CR8","doi-asserted-by":"crossref","unstructured":"Cohen-Addad, V., de Verdi\u00e8re, \u00c9.C., Klein, P.N., Mathieu, C., Meierfrankenfeld, D.: Approximating connectivity domination in weighted bounded-genus graphs. In: Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, pp. 584\u2013597. ACM (2016)","DOI":"10.1145\/2897518.2897635"},{"issue":"1","key":"31_CR9","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1016\/0890-5401(90)90043-H","volume":"85","author":"B Courcelle","year":"1990","unstructured":"Courcelle, B.: The monadic second-order logic of graphs. I. Recognizable sets of finite graphs. Inf. Comput. 85(1), 12\u201375 (1990)","journal-title":"Inf. Comput."},{"key":"31_CR10","unstructured":"Demaine, E.D., Hajiaghayi, M.: Bidimensionality: new connections between FPT algorithms and PTASs. In: Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2005, pp. 590\u2013601 (2005)"},{"issue":"1","key":"31_CR11","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. 162(1), 439\u2013485 (2005)","journal-title":"Ann. Math."},{"issue":"2","key":"31_CR12","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1137\/S0895480195291874","volume":"13","author":"G Even","year":"2000","unstructured":"Even, G., Naor, J., Schieber, B., Zosin, L.: Approximating minimum subset feedback sets in undirected graphs with applications. SIAM J. Discrete Math. 13(2), 255\u2013267 (2000)","journal-title":"SIAM J. Discrete Math."},{"key":"31_CR13","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Lokshtanov, D., Raman, V., Saurabh, S.: Bidimensionality and EPTAS. In: Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, pp. 748\u2013759 (2011)","DOI":"10.1137\/1.9781611973082.59"},{"key":"31_CR14","doi-asserted-by":"publisher","first-page":"1004","DOI":"10.1137\/0216064","volume":"16","author":"G Frederickson","year":"1987","unstructured":"Frederickson, G.: Fast algorithms for shortest paths in planar graphs with applications. SIAM J. Comput. 16, 1004\u20131022 (1987)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"31_CR15","doi-asserted-by":"publisher","first-page":"391","DOI":"10.1016\/0196-6774(84)90019-1","volume":"5","author":"JR Gilbert","year":"1984","unstructured":"Gilbert, J.R., Hutchinson, J.P., Tarjan, R.E.: A separator theorem for graphs of bounded genus. J. Algorithms 5(3), 391\u2013407 (1984)","journal-title":"J. Algorithms"},{"key":"31_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"717","DOI":"10.1007\/978-3-662-48350-3_60","volume-title":"Algorithms \u2013 ESA 2015","author":"S Har-Peled","year":"2015","unstructured":"Har-Peled, S., Quanrud, K.: Approximation algorithms for polynomial-expansion and low-density graphs. In: Bansal, N., Finocchi, I. (eds.) ESA 2015. LNCS, vol. 9294, pp. 717\u2013728. Springer, Heidelberg (2015). https:\/\/doi.org\/10.1007\/978-3-662-48350-3_60"},{"issue":"3","key":"31_CR17","doi-asserted-by":"publisher","first-page":"438","DOI":"10.1016\/0196-6774(87)90021-6","volume":"8","author":"DS Johnson","year":"1987","unstructured":"Johnson, D.S.: The NP-completeness column: an ongoing guide (column 19). J. Algorithms 8(3), 438\u2013448 (1987)","journal-title":"J. Algorithms"},{"key":"31_CR18","series-title":"The IBM Research Symposia Series","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of Computer Computations","author":"RM Karp","year":"1972","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W., Bohlinger, J.D. (eds.) Complexity of Computer Computations. IRSS, pp. 85\u2013103. Springer, Boston (1972). https:\/\/doi.org\/10.1007\/978-1-4684-2001-2_9"},{"key":"31_CR19","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1006\/jagm.2000.1137","volume":"38","author":"J Kleinberg","year":"2001","unstructured":"Kleinberg, J., Kumar, A.: Wavelength conversion in optical networks. J. Algorithms 38, 25\u201350 (2001)","journal-title":"J. Algorithms"},{"key":"31_CR20","first-page":"37","volume":"38","author":"AV Kostochka","year":"1982","unstructured":"Kostochka, A.V.: The minimum hadwiger number for graphs with a given mean degree of vertices. Metody Diskretnogo Analiza 38, 37\u201358 (1982). (in Russian)","journal-title":"Metody Diskretnogo Analiza"},{"issue":"4","key":"31_CR21","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1007\/BF02579141","volume":"4","author":"AV Kostochka","year":"1984","unstructured":"Kostochka, A.V.: Lower bound of the hadwiger number of graphs by their average degree. Combinatorica 4(4), 307\u2013316 (1984)","journal-title":"Combinatorica"},{"issue":"2","key":"31_CR22","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1137\/0136016","volume":"36","author":"R Lipton","year":"1979","unstructured":"Lipton, R., Tarjan, R.: A separator theorem for planar graphs. SIAM J. Appl. Math. 36(2), 177\u2013189 (1979)","journal-title":"SIAM J. Appl. Math."},{"key":"31_CR23","volume-title":"Theoretical Aspects of Local Search","author":"W Michiels","year":"2010","unstructured":"Michiels, W., Aarts, E., Korst, J.: Theoretical Aspects of Local Search. Springer, Heidelberg (2010)"},{"issue":"1","key":"31_CR24","doi-asserted-by":"publisher","first-page":"6","DOI":"10.1137\/S089548019529248X","volume":"12","author":"B Mohar","year":"1999","unstructured":"Mohar, B.: A linear time algorithm for embedding graphs in an arbitrary surface. SIAM J. Discrete Math. 12(1), 6\u201326 (1999)","journal-title":"SIAM J. Discrete Math."},{"issue":"4","key":"31_CR25","doi-asserted-by":"publisher","first-page":"883","DOI":"10.1007\/s00454-010-9285-9","volume":"44","author":"NH Mustafa","year":"2010","unstructured":"Mustafa, N.H., Ray, S.: Improved results on geometric hitting set problems. Discrete Comput. Geom. 44(4), 883\u2013895 (2010)","journal-title":"Discrete Comput. Geom."},{"issue":"3","key":"31_CR26","doi-asserted-by":"publisher","first-page":"607","DOI":"10.1007\/s00454-016-9819-x","volume":"57","author":"N Bus","year":"2017","unstructured":"Bus, N., Garg, S., Mustafa, N.H., Ray, S.: Limits of local search: quality and efficiency. Discrete Comput. Geom. 57(3), 607\u2013624 (2017)","journal-title":"Discrete Comput. Geom."},{"issue":"11","key":"31_CR27","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1140\/epjb\/e2014-50289-7","volume":"87","author":"S Qin","year":"2014","unstructured":"Qin, S., Zhou, H.: Solving the undirected feedback vertex set problem by local search. Eur. Phys. J. B 87(11), 273 (2014)","journal-title":"Eur. Phys. J. B"},{"issue":"1","key":"31_CR28","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/0095-8956(83)90079-5","volume":"35","author":"N Robertson","year":"1983","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. I. Excluding a forest. J. Comb. Theory Ser. B 35(1), 39\u201361 (1983)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"1","key":"31_CR29","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1016\/S0095-8956(03)00042-X","volume":"89","author":"N Robertson","year":"2003","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. XVI. Excluding a non-planar graph. J. Comb. Theory Ser. B 89(1), 43\u201376 (2003)","journal-title":"J. Comb. Theory Ser. B"},{"key":"31_CR30","doi-asserted-by":"crossref","unstructured":"Yannakakis, M.: Node-and edge-deletion NP-complete problems. In: Proceedings of the Tenth Annual ACM Symposium on Theory of Computing, pp. 253\u2013264. ACM (1978)","DOI":"10.1145\/800133.804355"},{"issue":"4","key":"31_CR31","doi-asserted-by":"publisher","first-page":"726","DOI":"10.3390\/a6040726","volume":"6","author":"Z Zhang","year":"2013","unstructured":"Zhang, Z., Ye, A., Zhou, X., Shao, Z.: An efficient local search for the feedback vertex set problem. Algorithms 6(4), 726\u2013746 (2013)","journal-title":"Algorithms"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-26176-4_31","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,7]],"date-time":"2024-03-07T15:13:26Z","timestamp":1709824406000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-26176-4_31"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019]]},"ISBN":["9783030261757","9783030261764"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-26176-4_31","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2019]]},"assertion":[{"value":"21 July 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"COCOON","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Computing and Combinatorics Conference","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Xi'an","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"China","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2019","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"29 July 2019","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"31 July 2019","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"25","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"cocoon2019a","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/ictt.xidian.edu.cn\/COCOON2019\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}