{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T19:13:27Z","timestamp":1743102807242,"version":"3.40.3"},"publisher-location":"Cham","reference-count":17,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319193144"},{"type":"electronic","value":"9783319193151"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"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":[[2015]]},"DOI":"10.1007\/978-3-319-19315-1_31","type":"book-chapter","created":{"date-parts":[[2015,6,6]],"date-time":"2015-06-06T10:42:08Z","timestamp":1433587328000},"page":"351-363","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Deterministic Algorithms for the Independent Feedback Vertex Set Problem"],"prefix":"10.1007","author":[{"given":"Yuma","family":"Tamura","sequence":"first","affiliation":[]},{"given":"Takehiro","family":"Ito","sequence":"additional","affiliation":[]},{"given":"Xiao","family":"Zhou","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,6,7]]},"reference":[{"key":"31_CR1","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, 289\u2013297 (1999)","journal-title":"SIAM J. Discrete Math."},{"key":"31_CR2","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, 942\u2013959 (1998)","journal-title":"SIAM J. Comput."},{"key":"31_CR3","doi-asserted-by":"publisher","first-page":"1305","DOI":"10.1137\/S0097539793251219","volume":"25","author":"HL Bodlaender","year":"1996","unstructured":"Bodlaender, H.L.: A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput. 25, 1305\u20131317 (1996)","journal-title":"SIAM J. Comput."},{"key":"31_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"196","DOI":"10.1007\/978-3-642-39206-1_17","volume-title":"Automata, Languages, and Programming","author":"HL Bodlaender","year":"2013","unstructured":"Bodlaender, H.L., Cygan, M., Kratsch, S., Nederlof, J.: Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth. In: Fomin, F.V., Freivalds, R., Kwiatkowska, M., Peleg, D. (eds.) ICALP 2013, Part I. LNCS, vol. 7965, pp. 196\u2013207. Springer, Heidelberg (2013)"},{"key":"31_CR5","doi-asserted-by":"crossref","unstructured":"Bodlaender, H.L., Drange, P.G., Dregi, M.S., Fomin, F.V., Lokshtanov, D., Pilipczuk, M.: An $$O(c^k n)$$\n                  $$5$$-approximation algorithm for treewidth. In: Proceedings of FOCS 2013, pp. 499\u2013508 (2013)","DOI":"10.1109\/FOCS.2013.60"},{"key":"31_CR6","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719796","volume-title":"Graph Classes: A Survey","author":"A Brandst\u00e4dt","year":"1999","unstructured":"Brandst\u00e4dt, A., Le, V.B., Spinrad, J.P.: Graph Classes: A Survey. SIAM, Philadelphia (1999)"},{"key":"31_CR7","first-page":"193","volume-title":"Handbook of Theoretical Computer Science","author":"B Courcelle","year":"1990","unstructured":"Courcelle, B.: Graph rewriting: an algebraic and logic approach. In: van Leeuwen, J. (ed.) Handbook of Theoretical Computer Science, vol. B, pp. 193\u2013242. MIT Press, Cambridge (1990)"},{"key":"31_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"386","DOI":"10.1007\/11682462_37","volume-title":"LATIN 2006: Theoretical Informatics","author":"F Dorn","year":"2006","unstructured":"Dorn, F., Telle, J.A.: Two birds with one stone: the best of branchwidth and treewidth with one algorithm. In: Correa, J.R., Hevia, A., Kiwi, M. (eds.) LATIN 2006. LNCS, vol. 3887, pp. 386\u2013397. Springer, Heidelberg (2006)"},{"key":"31_CR9","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1007\/978-1-4757-3023-4_4","volume-title":"Handbook of Combinatorial Optimization","author":"P Festa","year":"1999","unstructured":"Festa, P., Pardalos, P.M., Resende, M.G.C.: Feedback set problems. In: Du, D.-Z., Pardalos, P.M. (eds.) Handbook of Combinatorial Optimization, pp. 209\u2013258. Kluwer Academic Publishers, Dordrecht (1999)"},{"key":"31_CR10","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1137\/S0097539702419649","volume":"36","author":"FV Fomin","year":"2006","unstructured":"Fomin, F.V., Thilikos, D.M.: Dominating sets in planar graphs: branch-width and exponential speed-up. SIAM J. Comput. 36, 281\u2013309 (2006)","journal-title":"SIAM J. Comput."},{"key":"31_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"282","DOI":"10.1007\/3-540-36379-3_25","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"T Kloks","year":"2002","unstructured":"Kloks, T., Lee, C.M., Liu, J.: New algorithms for $$k$$-face cover, $$k$$-feedback vertex set, and $$k$$-disjoint cycles on plane and planar graphs. In: Ku\u010dera, L. (ed.) WG 2002. LNCS, vol. 2573, pp. 282\u2013295. Springer, Heidelberg (2002)"},{"key":"31_CR12","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1007\/s00453-011-9554-x","volume":"64","author":"M Lampis","year":"2012","unstructured":"Lampis, M.: Algorithmic meta-theorems for restrictions of treewidth. Algorithmica 64, 19\u201337 (2012)","journal-title":"Algorithmica"},{"key":"31_CR13","doi-asserted-by":"publisher","first-page":"198","DOI":"10.1016\/j.dam.2004.02.017","volume":"145","author":"RM McConnell","year":"2005","unstructured":"McConnell, R.M., Spinrad, J.P.: Linear-time modular decomposition of directed graphs. Discrete Appl. Math. 145, 198\u2013209 (2005)","journal-title":"Discrete Appl. Math."},{"key":"31_CR14","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. Theoret. Comput. Sci. 461, 65\u201375 (2012)","journal-title":"Theoret. Comput. Sci."},{"key":"31_CR15","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1016\/0196-6774(86)90023-4","volume":"7","author":"N Robertson","year":"1986","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. II. Algorithmic aspects of tree-width. J. Algorithms 7, 309\u2013322 (1986)","journal-title":"J. Algorithms"},{"key":"31_CR16","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1016\/j.tcs.2014.03.031","volume":"535","author":"Y Song","year":"2014","unstructured":"Song, Y.: An improved parameterized algorithm for the independent feedback vertex set problem. Theoret. Comput. Sci. 535, 25\u201330 (2014)","journal-title":"Theoret. Comput. Sci."},{"key":"31_CR17","doi-asserted-by":"publisher","first-page":"405","DOI":"10.1002\/jgt.3190120311","volume":"12","author":"E Speckenmeyer","year":"1988","unstructured":"Speckenmeyer, E.: On feedback vertex sets and nonseparating independent sets in cubic graphs. J. Graph Theory 12, 405\u2013412 (1988)","journal-title":"J. Graph Theory"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-19315-1_31","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,10]],"date-time":"2023-02-10T08:24:36Z","timestamp":1676017476000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-19315-1_31"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319193144","9783319193151"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-19315-1_31","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"7 June 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}