{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,12]],"date-time":"2026-05-12T11:20:20Z","timestamp":1778584820502,"version":"3.51.4"},"reference-count":10,"publisher":"Elsevier BV","issue":"4-5","license":[{"start":{"date-parts":[[1998,5,1]],"date-time":"1998-05-01T00:00:00Z","timestamp":893980800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Operations Research Letters"],"published-print":{"date-parts":[[1998,5]]},"DOI":"10.1016\/s0167-6377(98)00021-2","type":"journal-article","created":{"date-parts":[[2002,7,25]],"date-time":"2002-07-25T12:16:06Z","timestamp":1027599366000},"page":"111-118","source":"Crossref","is-referenced-by-count":69,"title":["A primal\u2013dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs"],"prefix":"10.1016","volume":"22","author":[{"given":"Fabi\u00e1n A.","family":"Chudak","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michel X.","family":"Goemans","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dorit S.","family":"Hochbaum","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David P.","family":"Williamson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/S0167-6377(98)00021-2_BIB1","doi-asserted-by":"crossref","unstructured":"V. Bafna, P. Berman, T. Fujito, Constant ratio approximation of the weighted feedback vertex set problem for undirected graphs, in: J. Staples, P. Eades, N. Katoh, A. Moffat (Eds.), ISAAC \u201995 Algorithms and Computation, number 1004 in Lecture Notes in Computer Science, Springer, Berlin, 1995, pp. 142\u2013151.","DOI":"10.1007\/BFb0015417"},{"key":"10.1016\/S0167-6377(98)00021-2_BIB2","unstructured":"R. Bar-Yehuda, D. Geiger, J. Naor, R.M. Roth, Approximation algorithms for the vertex feedback set problem with applications to constraint satisfaction and Bayesian inference, in: Proc. 5th Ann. ACM-SIAM Symp. on Discrete Algorithms, 1994, pp. 344\u2013354."},{"key":"10.1016\/S0167-6377(98)00021-2_BIB3","doi-asserted-by":"crossref","unstructured":"A. Becker, D. Geiger, Approximation algorithms for the loop cutset problem, in: Proc. 10th Conf. on Uncertainty in Artificial Intelligence, 1994, pp. 60\u201368. Update: A. Becker, D. Geiger: Optimization of Pearl's method of conditioning and greedy-like approximation algorithms for the vertex feedback set problem, Artificial Intelligence 83 (1996), 167\u2013188.","DOI":"10.1016\/0004-3702(95)00004-6"},{"key":"10.1016\/S0167-6377(98)00021-2_BIB4","unstructured":"G. Even, J. Naor, B. Schieber, L. Zosin, Approximating minimum subset feedback sets in undirected graphs with applications, in: Proc. 4th Israel Symp. on Theory of Computing and Systems, 1996, pp. 78\u201388."},{"key":"10.1016\/S0167-6377(98)00021-2_BIB5","unstructured":"M.R. Garey, D.S. Johnson, Computers and Intractability, W.H. Freeman and Company, New York, 1979."},{"key":"10.1016\/S0167-6377(98)00021-2_BIB6","doi-asserted-by":"crossref","unstructured":"M.X. Goemans, D.P. Williamson, Primal\u2013dual approximation algorithms for feedback problems in planar graphs, in: W.H. Cunningham, S.T. McCormick, M. Queyranne (Eds.), Integer Programming and Combinatorial Optimization, number 1084, in Lecture Notes in Computer Science, Springer, Berlin, 1996, pp. 147\u2013161, to appear in Combinatorica.","DOI":"10.1007\/3-540-61310-2_12"},{"key":"10.1016\/S0167-6377(98)00021-2_BIB7","unstructured":"M.X. Goemans, D.P. Williamson, The primal\u2013dual method for approximation algorithms and its application to network design problems, in: D.S. Hochbaum (Ed.), Approximation Algorithms for NP-hard Problems, Ch. 4, PWS, Boston, 1996."},{"key":"10.1016\/S0167-6377(98)00021-2_BIB8","unstructured":"D.S. Hochbaum, Approximating covering and packing problems: Set cover, vertex cover, independent set, and related problems, in: D.S. Hochbaum (Ed.), Approximation Algorithms for NP-hard Problems, Ch. 3, PWS, Boston, 1996."},{"key":"10.1016\/S0167-6377(98)00021-2_BIB9","unstructured":"P. Klein, R. Ravi, When cycles collapse: a general approximation technique for constrained two-connectivity problems, in: Proc. 3rd MPS Conf. on Integer Programming and Combinatorial Optimization, 1993, pp. 39\u201355, also appears as Brown University Technical Report CS-92-30, to appear in Algorithmica."},{"key":"10.1016\/S0167-6377(98)00021-2_BIB10","doi-asserted-by":"crossref","first-page":"435","DOI":"10.1007\/BF01299747","article-title":"A primal\u2013dual approximation algorithm for generalized Steiner network problems","volume":"15","author":"Williamson","year":"1995","journal-title":"Combinatorica"}],"container-title":["Operations Research Letters"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0167637798000212?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0167637798000212?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,4,26]],"date-time":"2019-04-26T03:20:38Z","timestamp":1556248838000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0167637798000212"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998,5]]},"references-count":10,"journal-issue":{"issue":"4-5","published-print":{"date-parts":[[1998,5]]}},"alternative-id":["S0167637798000212"],"URL":"https:\/\/doi.org\/10.1016\/s0167-6377(98)00021-2","relation":{},"ISSN":["0167-6377"],"issn-type":[{"value":"0167-6377","type":"print"}],"subject":[],"published":{"date-parts":[[1998,5]]}}}