{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,7]],"date-time":"2025-10-07T14:29:47Z","timestamp":1759847387703},"reference-count":21,"publisher":"Elsevier BV","issue":"1-3","license":[{"start":{"date-parts":[[2000,4,1]],"date-time":"2000-04-01T00:00:00Z","timestamp":954547200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,17]],"date-time":"2013-07-17T00:00:00Z","timestamp":1374019200000},"content-version":"vor","delay-in-days":4855,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Applied Mathematics"],"published-print":{"date-parts":[[2000,4]]},"DOI":"10.1016\/s0166-218x(99)00180-8","type":"journal-article","created":{"date-parts":[[2002,7,25]],"date-time":"2002-07-25T16:21:11Z","timestamp":1027614071000},"page":"37-51","source":"Crossref","is-referenced-by-count":16,"title":["Solving the feedback vertex set problem on undirected graphs"],"prefix":"10.1016","volume":"101","author":[{"given":"Lorenzo","family":"Brunetta","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Francesco","family":"Maffioli","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marco","family":"Trubian","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/S0166-218X(99)00180-8_BIB1","doi-asserted-by":"crossref","unstructured":"V. Bafna, P. Berman, T. Fujito, Constant ratio approximations of the feedback vertex set problem for undirected graphs, in: J. Staples P. Eades, N. Katoh, A. Moffat (Eds.), ISAC 95, Algorithms and Computation, 1995, pp. 142\u2013151.","DOI":"10.1007\/BFb0015417"},{"key":"10.1016\/S0166-218X(99)00180-8_BIB2","unstructured":"R. Bar-Yehuda, D. Geiger, J. Naor, R.M. Roth, Approximation algorithms for the feedback vertex set problem with applications to constraint satisfaction and Bayesian inference, Proceedings of the 5th Annual ACM SIAM Symposium on Discrete Algorithms, 1994, pp. 344\u2013354."},{"key":"10.1016\/S0166-218X(99)00180-8_BIB3","doi-asserted-by":"crossref","unstructured":"A. Becker, D. Geiger, Approximation algorithms for the loop cutset problem, in: Proceedings of the 10th Conference on Uncertainty in Artificial Intelligence, 1994, pp. 60\u201368.","DOI":"10.1016\/B978-1-55860-332-5.50013-4"},{"key":"10.1016\/S0166-218X(99)00180-8_BIB4","unstructured":"S. Ceria, P. Nobili, A. Sassano, Set covering problem, in: M. Dell'Amico, S. Martello, F. Maffioli (Eds.), Annotated Bibliographies in Combinatorial Optimization, Wiley, Chichester, 1997, pp. 415\u2013428."},{"key":"10.1016\/S0166-218X(99)00180-8_BIB5","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1016\/S0167-6377(98)00021-2","article-title":"A primal\u2013dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs","volume":"22","author":"Chudak","year":"1998","journal-title":"Oper. Res. Lett."},{"key":"10.1016\/S0166-218X(99)00180-8_BIB6","first-page":"515","article-title":"A greedy heuristic for the set covering","volume":"7","author":"Chv\u00e1tal","year":"1979","journal-title":"Math. Oper. Res."},{"key":"10.1016\/S0166-218X(99)00180-8_BIB7","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1002\/net.3230260205","article-title":"Feedback vertex set on cocomparability graphs","volume":"26","author":"Coorg","year":"1995","journal-title":"Networks"},{"key":"10.1016\/S0166-218X(99)00180-8_BIB8","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1016\/0004-3702(90)90046-3","article-title":"Enhancement schemes for constraint processing: backjumping, learning and cutset decomposition","volume":"41","author":"Dechter","year":"1990","journal-title":"Artificial Intell."},{"key":"10.1016\/S0166-218X(99)00180-8_BIB9","unstructured":"M. Dell'Amico, A. Lodi, F. Maffioli, Solution of the cumulative assignment problem with a new tabu search method, J. Heuristics (1997), to appear."},{"key":"10.1016\/S0166-218X(99)00180-8_BIB10","doi-asserted-by":"crossref","first-page":"500","DOI":"10.1016\/S0377-2217(97)00287-7","article-title":"Solution of large weighted equicut problems","volume":"106","author":"Dell'Amico","year":"1998","journal-title":"European J. Oper. Res."},{"key":"10.1016\/S0166-218X(99)00180-8_BIB11","doi-asserted-by":"crossref","unstructured":"M. Funke, G. Reinelt, A polyhedral approach to the feedback vertex set problem, in: Proc. 5th Int. IPCO Conf., Vancouver, 1996, pp. 445\u2013459.","DOI":"10.1007\/3-540-61310-2_33"},{"key":"10.1016\/S0166-218X(99)00180-8_BIB12","doi-asserted-by":"crossref","first-page":"190","DOI":"10.1287\/ijoc.1.3.190","article-title":"Tabu search \u2014 Part 1","volume":"1","author":"Glover","year":"1989","journal-title":"ORSA J. Comput."},{"key":"10.1016\/S0166-218X(99)00180-8_BIB13","unstructured":"D.S. Hochbaum, Various notions of approximations: good, better, best, and more, in: D.S. Hochbaum (Ed.), Approximation Algorithms for NP-hard Problems PWS, Boston, 1996, pp. 347\u2013363."},{"key":"10.1016\/S0166-218X(99)00180-8_BIB14","doi-asserted-by":"crossref","unstructured":"R.M. Karp, Reducibility among combinatorial problems, in: R. Miller, J. Thatcher (Eds.), Complexity of Computer Computations, Plenum Press, New York, 1972, pp. 85\u2013103.","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"10.1016\/S0166-218X(99)00180-8_BIB15","first-page":"559","article-title":"Generating all maximal independent sets: NP-hardness and polynomial time algorithms","volume":"9\/3","author":"Lawler","year":"1980","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0166-218X(99)00180-8_BIB16","doi-asserted-by":"crossref","first-page":"292","DOI":"10.1016\/0022-0000(88)90009-8","article-title":"On locating minimum feedback vertex sets","volume":"37","author":"Llyod","year":"1988","journal-title":"J. Comput. Systems Sci."},{"key":"10.1016\/S0166-218X(99)00180-8_BIB17","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1016\/S0020-0190(98)00039-8","article-title":"Almost exact minimum feedback vertex set in meshes and butterflies","volume":"66","author":"Luccio","year":"1998","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/S0166-218X(99)00180-8_BIB18","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1016\/S0020-0190(96)00193-7","article-title":"A linear-time algorithm for the weighted feedback vertex problem on interval graphs","volume":"61","author":"Lu","year":"1997","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/S0166-218X(99)00180-8_BIB19","unstructured":"D. Peleg, Local majority voting, small coalitions and controlling monopolies in graphs: a review, in: Proceeding of 3rd Colloqium on Structural Information and Communications Complexity, 1996, pp. 152\u2013169."},{"key":"10.1016\/S0166-218X(99)00180-8_BIB20","unstructured":"D. Peleg, Size bounds for dynamic monopolies, Proceeding of 4th Colloqium on Structural Information and Communications Complexity, 1997, pp. 165\u2013175."},{"key":"10.1016\/S0166-218X(99)00180-8_BIB21","doi-asserted-by":"crossref","first-page":"296","DOI":"10.1145\/3149.3159","article-title":"Feedback vertex set and cyclically reducible graphs","volume":"32","author":"Wang","year":"1985","journal-title":"J. ACM"}],"container-title":["Discrete Applied Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0166218X99001808?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0166218X99001808?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,4,26]],"date-time":"2019-04-26T04:56:17Z","timestamp":1556254577000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0166218X99001808"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000,4]]},"references-count":21,"journal-issue":{"issue":"1-3","published-print":{"date-parts":[[2000,4]]}},"alternative-id":["S0166218X99001808"],"URL":"https:\/\/doi.org\/10.1016\/s0166-218x(99)00180-8","relation":{},"ISSN":["0166-218X"],"issn-type":[{"value":"0166-218X","type":"print"}],"subject":[],"published":{"date-parts":[[2000,4]]}}}