{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,12]],"date-time":"2026-05-12T11:19:29Z","timestamp":1778584769852,"version":"3.51.4"},"reference-count":19,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2014,4,19]],"date-time":"2014-04-19T00:00:00Z","timestamp":1397865600000},"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":["J Comb Optim"],"published-print":{"date-parts":[[2015,8]]},"DOI":"10.1007\/s10878-014-9737-x","type":"journal-article","created":{"date-parts":[[2014,4,18]],"date-time":"2014-04-18T14:52:02Z","timestamp":1397832722000},"page":"214-241","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["An improved exact algorithm for undirected feedback vertex set"],"prefix":"10.1007","volume":"30","author":[{"given":"Mingyu","family":"Xiao","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hiroshi","family":"Nagamochi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2014,4,19]]},"reference":[{"issue":"3","key":"9737_CR1","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1137\/S0895480196305124","volume":"12","author":"V Bafna","year":"1999","unstructured":"Bafna V, Berman P, Fujito T (1999) A 2-approximation algorithm for the undirected feedback vertex set problem. SIAM J Discret Math 12(3):289\u2013297","journal-title":"SIAM J Discret Math"},{"issue":"1\u20132","key":"9737_CR2","doi-asserted-by":"crossref","first-page":"382","DOI":"10.1007\/s00453-010-9460-7","volume":"62","author":"N Bourgeois","year":"2012","unstructured":"Bourgeois N, Escoffier B, Paschos VT, van Rooij JMM (2012) Fast algorithms for max independent set. Algorithmica 62(1\u20132):382\u2013415","journal-title":"Algorithmica"},{"key":"9737_CR3","doi-asserted-by":"crossref","unstructured":"Cao Y, Chen J, Liu Y (2010) On feedback vertex set new measure and new structures. In: Kaplan H (ed) Algorithm Theory - SWAT 2010. LNCS, vol 6139. Springer, Heidelberg, pp 93\u2013104","DOI":"10.1007\/978-3-642-13731-0_10"},{"key":"9737_CR4","doi-asserted-by":"crossref","first-page":"1188","DOI":"10.1016\/j.jcss.2008.05.002","volume":"74","author":"J Chen","year":"2008","unstructured":"Chen J, Fomin F, Liu Y, Lu S, Villanger Y (2008) Improved algorithms for feedback vertex set problems. J. Comput. Syst. Sci. 74:1188\u20131198","journal-title":"J. Comput. Syst. Sci."},{"key":"9737_CR5","first-page":"1","volume":"55","author":"J Chen","year":"2008","unstructured":"Chen J, Liu Y, Lu S, O\u2019Sullivan B, Razgon I (2008) A fixed-parameter algorithm for the directed feedback vertex set problem. J. ACM 55:1\u201319","journal-title":"J. ACM"},{"key":"9737_CR6","doi-asserted-by":"crossref","unstructured":"Dehne F, Fellows M, Langston M, Rosamond F, Stevens K (2005) An $$O(2^{O(k)}n^3)$$ O ( 2 O ( k ) n 3 ) FPT algorithm for the undirected feedback vertex set problem. In: Wang L (ed) COCOON 2005. LNCS, vol 3595. Springer, Heidelberg, pp 859\u2013869","DOI":"10.1007\/11533719_87"},{"key":"9737_CR7","unstructured":"Dwork C, Kumar R, Naor M, Sivakumar D (2001) Rank aggregation revisited. Manuscript"},{"key":"9737_CR8","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1007\/PL00009191","volume":"20","author":"G Even","year":"1998","unstructured":"Even G, Naor J, Schieber B, Sudan M (1998) Approximating minimum feedback sets and multicuts in directed graphs. Algorithmica 20:151\u2013174","journal-title":"Algorithmica"},{"key":"9737_CR9","doi-asserted-by":"crossref","unstructured":"Festa P, Pardalos PM, Resende MGC (1999) Feedback set problems. In: Handbook of Combinatorial Optimization. Kluwer Acad. Publ., Dordrecht, pp 209\u2013258","DOI":"10.1007\/978-1-4757-3023-4_4"},{"issue":"2","key":"9737_CR10","doi-asserted-by":"crossref","first-page":"293","DOI":"10.1007\/s00453-007-9152-0","volume":"52","author":"FV Fomin","year":"2008","unstructured":"Fomin FV, Gaspers S, Pyatkin AV, Razgon I (2008) On the minimum feedback vertex set problem: exact and enumeration algorithms. Algorithmica 52(2):293\u2013307","journal-title":"Algorithmica"},{"issue":"5","key":"9737_CR11","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1552285.1552286","volume":"56","author":"FV Fomin","year":"2009","unstructured":"Fomin FV, Grandoni F, Kratsch D (2009) A measure & conquer approach for the analysis of exact algorithms. J. ACM 56(5):1\u201332","journal-title":"J. ACM"},{"key":"9737_CR12","doi-asserted-by":"crossref","first-page":"1386","DOI":"10.1016\/j.jcss.2006.02.001","volume":"72","author":"J Guo","year":"2006","unstructured":"Guo J, Gramm J, Huffner F, Niedermeier R, Wernicke S (2006) Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization. J. Comput. Syst. Sci. 72:1386\u20131396","journal-title":"J. Comput. Syst. Sci."},{"key":"9737_CR13","doi-asserted-by":"crossref","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 RM (1972) Reducibility among combinatorial problems. In: Miller RM, Thatcher JW (eds) Complexity of computer computations. Plenum Press, New York, pp 85\u2013103"},{"key":"9737_CR14","volume-title":"Mathematical models in the social sciences","author":"J Kemeny","year":"1962","unstructured":"Kemeny J, Snell J (1962) Mathematical models in the social sciences. Blaisdell, Boston"},{"key":"9737_CR15","volume-title":"Operating system concepts","author":"A Silberschatz","year":"1994","unstructured":"Silberschatz A, Galvin P (1994) Operating system concepts, 4th edn. Addison-Wesley, New York","edition":"4"},{"key":"9737_CR16","doi-asserted-by":"crossref","unstructured":"Razgon I (2006) Exact computation of maximum induced forest. In: Proceedings of the 10th Scandinavian workshop on algorithm theory (SWAT 2006). LNCS, vol 4059. Springer, Heidelberg, pp 161\u2013171","DOI":"10.1007\/11785293_17"},{"key":"9737_CR17","doi-asserted-by":"crossref","unstructured":"Razgon I (2007) Computing minimum directed feedback vertex set in $$O(1.9977^n)$$ O ( 1 . 9977 n ) . In: Theoretical computer science, 10th Italian conference. ICTCS 2007. Rome, Italy, pp 70\u201381","DOI":"10.1142\/9789812770998_0010"},{"key":"9737_CR18","doi-asserted-by":"crossref","unstructured":"Xiao M, Nagamochi H (2012) A refined exact algorithm for edge dominating set. TAMC 2012. LNCS, vol 7287. Springer, Heidelberg, pp 360\u2013372","DOI":"10.1007\/978-3-642-29952-0_36"},{"key":"9737_CR19","doi-asserted-by":"crossref","unstructured":"Xiao M, Nagamochi H (2013) Exact algorithms for maximum independent set. ISAAC 2013. LNCS, vol 8283. Springer, Heidelberg, pp 328\u2013338","DOI":"10.1007\/978-3-642-45030-3_31"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-014-9737-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-014-9737-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-014-9737-x","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,9]],"date-time":"2019-08-09T13:38:28Z","timestamp":1565357908000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-014-9737-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,4,19]]},"references-count":19,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2015,8]]}},"alternative-id":["9737"],"URL":"https:\/\/doi.org\/10.1007\/s10878-014-9737-x","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,4,19]]}}}