{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,11]],"date-time":"2024-09-11T12:52:12Z","timestamp":1726059132453},"publisher-location":"Cham","reference-count":36,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030340285"},{"type":"electronic","value":"9783030340292"}],"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-34029-2_7","type":"book-chapter","created":{"date-parts":[[2019,11,14]],"date-time":"2019-11-14T03:02:40Z","timestamp":1573700560000},"page":"98-113","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Engineering a PTAS for Minimum Feedback Vertex Set in Planar Graphs"],"prefix":"10.1007","author":[{"given":"Glencora","family":"Borradaile","sequence":"first","affiliation":[]},{"given":"Hung","family":"Le","sequence":"additional","affiliation":[]},{"given":"Baigong","family":"Zheng","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,11,14]]},"reference":[{"key":"7_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"264","DOI":"10.1007\/978-3-642-33293-7_25","volume-title":"Parameterized and Exact Computation","author":"FN Abu-Khzam","year":"2012","unstructured":"Abu-Khzam, F.N., Bou Khuzam, M.: An improved kernel for the undirected planar feedback vertex set problem. In: Thilikos, D.M., Woeginger, G.J. (eds.) IPEC 2012. LNCS, vol. 7535, pp. 264\u2013273. Springer, Heidelberg (2012). \nhttps:\/\/doi.org\/10.1007\/978-3-642-33293-7_25"},{"key":"7_CR2","first-page":"1","volume":"11","author":"L Aleksandrov","year":"2007","unstructured":"Aleksandrov, L., Djidjev, H., Guo, H., Maheshwari, A.: Partitioning planar graphs with costs and weights. J. Exp. Algorithm. (JEA) 11, 1\u20135 (2007)","journal-title":"J. Exp. Algorithm. (JEA)"},{"issue":"4","key":"7_CR3","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., Thomas, R.: A separator theorem for nonplanar graphs. J. Am. Math. Soc. 3(4), 801\u2013808 (1990)","journal-title":"J. Am. Math. Soc."},{"key":"7_CR4","unstructured":"Arora, S., Grigni, M., Karger, D.R., Klein, P.N., Woloszyn, A.: A polynomial-time approximation scheme for weighted planar graph TSP. In: SODA, vol. 98, pp. 33\u201341 (1998)"},{"issue":"1","key":"7_CR5","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1145\/174644.174650","volume":"41","author":"BS Baker","year":"1994","unstructured":"Baker, B.S.: Approximation algorithms for NP-complete problems on planar graphs. J. ACM (JACM) 41(1), 153\u2013180 (1994)","journal-title":"J. ACM (JACM)"},{"issue":"4","key":"7_CR6","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.M.: Approximation algorithms for the feedback vertex set problem with applications to constraint satisfaction and Bayesian inference. SIAM J. Comput. 27(4), 942\u2013959 (1998)","journal-title":"SIAM J. Comput."},{"issue":"5","key":"7_CR7","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1145\/2027216.2027219","volume":"58","author":"MH Bateni","year":"2011","unstructured":"Bateni, M.H., Hajiaghayi, M.T., Marx, D.: Approximation schemes for Steiner forest on planar graphs and graphs of bounded treewidth. J. ACM 58(5), 21 (2011)","journal-title":"J. ACM"},{"key":"7_CR8","unstructured":"Becker, A., Fox-Epstein, E., Klein, P.N., Meierfrankenfeld, D.: Engineering an approximation scheme for traveling salesman in planar graphs. In: LIPIcs-Leibniz International Proceedings in Informatics, vol. 75 (2017)"},{"issue":"1","key":"7_CR9","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":"5","key":"7_CR10","doi-asserted-by":"publisher","first-page":"44","DOI":"10.1145\/2973749","volume":"63","author":"HL Bodlaender","year":"2016","unstructured":"Bodlaender, H.L., Fomin, F.V., Lokshtanov, D., Penninkx, E., Saurabh, S., Thilikos, D.M.: (Meta) kernelization. J. ACM (JACM) 63(5), 44 (2016)","journal-title":"J. ACM (JACM)"},{"key":"7_CR11","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1016\/j.tcs.2016.05.031","volume":"645","author":"M Bonamy","year":"2016","unstructured":"Bonamy, M., Kowalik, \u0141.: A 13k-kernel for planar feedback vertex set via region decomposition. Theoret. Comput. Sci. 645, 25\u201340 (2016)","journal-title":"Theoret. Comput. Sci."},{"issue":"3","key":"7_CR12","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1541885.1541892","volume":"5","author":"G Borradaile","year":"2009","unstructured":"Borradaile, G., Klein, P., Mathieu, C.: An $${O}(n \\log n)$$ approximation scheme for Steiner tree in planar graphs. ACM Trans. Algorithms (TALG) 5(3), 1\u201331 (2009)","journal-title":"ACM Trans. Algorithms (TALG)"},{"issue":"2","key":"7_CR13","doi-asserted-by":"publisher","first-page":"241","DOI":"10.7155\/jgaa.00091","volume":"8","author":"JM Boyer","year":"2004","unstructured":"Boyer, J.M., Myrvold, W.J.: On the cutting edge: simplified $${O}(n)$$ planarity by edge addition. J. Graph Algorithms Appl. 8(2), 241\u2013273 (2004)","journal-title":"J. Graph Algorithms Appl."},{"issue":"4","key":"7_CR14","first-page":"203","volume":"4","author":"N Chiba","year":"1981","unstructured":"Chiba, N., Nishizeki, T., Saito, N.: Applications of the Lipton and Tarjan\u2019s planar separator theorem. J. Inf. Process. 4(4), 203\u2013207 (1981)","journal-title":"J. Inf. Process."},{"issue":"4","key":"7_CR15","doi-asserted-by":"publisher","first-page":"663","DOI":"10.1137\/0211055","volume":"11","author":"N Chiba","year":"1982","unstructured":"Chiba, N., Nishizeki, T., Saito, N.: An approximation algorithm for the maximum independent set problem on planar graphs. SIAM J. Comput. 11(4), 663\u2013675 (1982)","journal-title":"SIAM J. Comput."},{"key":"7_CR16","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"},{"key":"7_CR17","unstructured":"Demaine, E.D., Hajiaghayi, M.T., Kawarabayashi, K.-i.: Algorithmic graph minor theory: decomposition, approximation, and coloring. In: Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, pp. 637\u2013646 (2005)"},{"key":"7_CR18","unstructured":"Demaine, E.D., Hajiaghayi, M.T.: 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)"},{"key":"7_CR19","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-30162-4","volume-title":"Encyclopedia of Algorithms","author":"C Demetrescu","year":"2008","unstructured":"Demetrescu, C., Goldberg, A., Johnson, D.: Implementation challenge for shortest paths. In: Kao, M.Y. (ed.) Encyclopedia of Algorithms. Springer, Boston (2008). \nhttps:\/\/doi.org\/10.1007\/978-0-387-30162-4"},{"key":"7_CR20","doi-asserted-by":"crossref","unstructured":"Eisenstat, D., Klein, P., Mathieu, C.: An efficient polynomial-time approximation scheme for Steiner forest in planar graphs. In: Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 626\u2013638. SIAM (2012)","DOI":"10.1137\/1.9781611973099.53"},{"key":"7_CR21","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Lokshtanov, D., Saurabh, S., Thilikos, D.M.: Bidimensionality and kernels. In: Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 503\u2013510 (2010)","DOI":"10.1137\/1.9781611973075.43"},{"key":"7_CR22","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Lokshtanov, D., Saurabh, S., Thilikos, D.M.: Linear kernels for (connected) dominating set on H-minor-free graphs. In: Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 82\u201393 (2012)","DOI":"10.1137\/1.9781611973099.7"},{"key":"7_CR23","first-page":"2","volume":"21","author":"E Fox-Epstein","year":"2016","unstructured":"Fox-Epstein, E., Mozes, S., Phothilimthana, P.M., Sommer, C.: Short and simple cycle separators in planar graphs. J. Exp. Algorithm. (JEA) 21, 2 (2016)","journal-title":"J. Exp. Algorithm. (JEA)"},{"issue":"4","key":"7_CR24","doi-asserted-by":"publisher","first-page":"613","DOI":"10.1007\/s00493-003-0037-9","volume":"23","author":"M Grohe","year":"2003","unstructured":"Grohe, M.: Local tree-width, excluded minors, and approximation algorithms. Combinatorica 23(4), 613\u2013632 (2003)","journal-title":"Combinatorica"},{"key":"7_CR25","first-page":"5","volume":"14","author":"M Holzer","year":"2009","unstructured":"Holzer, M., Schulz, F., Wagner, D., Prasinos, G., Zaroliagis, C.: Engineering planar separator algorithms. J. Exp. Algorithm. (JEA) 14, 5 (2009)","journal-title":"J. Exp. Algorithm. (JEA)"},{"key":"7_CR26","unstructured":"Iwata, Y.: Linear-time kernelization for feedback vertex set. CoRR (2016)"},{"issue":"4","key":"7_CR27","doi-asserted-by":"publisher","first-page":"1377","DOI":"10.1137\/140962838","volume":"45","author":"Y Iwata","year":"2016","unstructured":"Iwata, Y., Wahlstr\u00f6m, M., Yoshida, Y.: Half-integrality, LP-branching, and FPT algorithms. SIAM J. Comput. 45(4), 1377\u20131411 (2016)","journal-title":"SIAM J. Comput."},{"key":"7_CR28","series-title":"The IBM Research Symposia Series","doi-asserted-by":"publisher","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. The IBM Research Symposia Series. Springer, Boston (1972). \nhttps:\/\/doi.org\/10.1007\/978-1-4684-2001-2_9"},{"issue":"6","key":"7_CR29","doi-asserted-by":"publisher","first-page":"1926","DOI":"10.1137\/060649562","volume":"37","author":"PN Klein","year":"2008","unstructured":"Klein, P.N.: A linear-time approximation scheme for TSP in undirected planar graphs with edge-weights. SIAM J. Comput. 37(6), 1926\u20131952 (2008)","journal-title":"SIAM J. Comput."},{"key":"7_CR30","volume-title":"The Design and Analysis of Algorithms","author":"DC Kozen","year":"2012","unstructured":"Kozen, D.C.: The Design and Analysis of Algorithms. Springer, Heidelberg (2012)"},{"key":"7_CR31","unstructured":"Le, H., Zheng, B.: Local search is a PTAS for feedback vertex set in minor-free graphs. CoRR, abs\/1804.06428 (2018)"},{"issue":"2","key":"7_CR32","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1137\/0136016","volume":"36","author":"RJ Lipton","year":"1979","unstructured":"Lipton, R.J., Tarjan, R.E.: A separator theorem for planar graphs. SIAM J. Appl. Math. 36(2), 177\u2013189 (1979)","journal-title":"SIAM J. Appl. Math."},{"issue":"3","key":"7_CR33","doi-asserted-by":"publisher","first-page":"615","DOI":"10.1137\/0209046","volume":"9","author":"RJ Lipton","year":"1980","unstructured":"Lipton, R.J., Tarjan, R.E.: Applications of a planar separator theorem. SIAM J. Comput. 9(3), 615\u2013627 (1980)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"7_CR34","doi-asserted-by":"publisher","first-page":"43","DOI":"10.3390\/a6010043","volume":"6","author":"M Marzban","year":"2013","unstructured":"Marzban, M., Qian-Ping, G.: Computational study on a PTAS for planar dominating set problem. Algorithms 6(1), 43\u201359 (2013)","journal-title":"Algorithms"},{"key":"7_CR35","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"7","DOI":"10.1007\/3-540-63165-8_161","volume-title":"Automata, Languages and Programming","author":"K Mehlhorn","year":"1997","unstructured":"Mehlhorn, K., N\u00e4her, S., Uhrig, C.: The LEDA platform for combinatorial and geometric computing. In: Degano, P., Gorrieri, R., Marchetti-Spaccamela, A. (eds.) ICALP 1997. LNCS, vol. 1256, pp. 7\u201316. Springer, Heidelberg (1997). \nhttps:\/\/doi.org\/10.1007\/3-540-63165-8_161"},{"key":"7_CR36","first-page":"3","volume":"16","author":"S Tazari","year":"2011","unstructured":"Tazari, S., M\u00fcller-Hannemann, M.: Dealing with large hidden constants: engineering a planar Steiner tree PTAS. J. Exp. Algorithm. (JEA) 16, 3\u20136 (2011)","journal-title":"J. Exp. Algorithm. (JEA)"}],"container-title":["Lecture Notes in Computer Science","Analysis of Experimental Algorithms"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-34029-2_7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,11,14]],"date-time":"2019-11-14T03:08:28Z","timestamp":1573700908000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-030-34029-2_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019]]},"ISBN":["9783030340285","9783030340292"],"references-count":36,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-34029-2_7","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":"14 November 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"SEA","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Symposium on Experimental Algorithms","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Kalamata","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Greece","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":"24 June 2019","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"29 June 2019","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"wea2019","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/www.caopt.com\/SEA2019\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"45","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"35","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"78% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"2","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"2","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"No","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}