{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,1]],"date-time":"2025-12-01T11:08:41Z","timestamp":1764587321131},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540605737"},{"type":"electronic","value":"9783540477662"}],"license":[{"start":{"date-parts":[[1995,1,1]],"date-time":"1995-01-01T00:00:00Z","timestamp":788918400000},"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":[[1995]]},"DOI":"10.1007\/bfb0015417","type":"book-chapter","created":{"date-parts":[[2005,11,13]],"date-time":"2005-11-13T01:50:06Z","timestamp":1131846606000},"page":"142-151","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":22,"title":["Constant ratio approximations of the weighted feedback vertex set problem for undirected graphs"],"prefix":"10.1007","author":[{"given":"Vineet","family":"Bafna","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Piotr","family":"Berman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Toshihiro","family":"Fujito","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,9]]},"reference":[{"key":"16_CR1","doi-asserted-by":"crossref","unstructured":"S. Arora, C. Lund, R. Motwani, and M. Sudan and M. Szegedy. Proof verification and intractability of approximation problems. In 33rd IEEE Symp. on Foundations of Computer Science, 1992.","DOI":"10.1109\/SFCS.1992.267823"},{"key":"16_CR2","doi-asserted-by":"crossref","unstructured":"Bar-Yehuda, R. and S. Even. A local-ratio theorem for approximating the weighted vertex cover problem. In Annals of Discrete Mathematics 25. North-Holland, 1985.","DOI":"10.1016\/S0304-0208(08)73101-3"},{"key":"16_CR3","unstructured":"R. Bar-Yehuda, D. Geiger, J. Naor and R. M. Roth. Approximation algorithms for the vertex feedback set problem with applications to constraint satisfaction and Bayesian inference. In Proc. of the 5th Annual ACM-SIAM Symp. on Discrete Algorithms, pages 344\u2013354, 1994."},{"key":"16_CR4","doi-asserted-by":"crossref","unstructured":"A. Becker and D. Geiger. Approximation algorithms for the loop cutset problem. In Uncertainity in Artificial Intelligence, 9, 1994.","DOI":"10.1016\/B978-1-55860-332-5.50013-4"},{"key":"16_CR5","unstructured":"P. Berman. [personal communication]"},{"key":"16_CR6","unstructured":"M. R. Garey and D. S. Johnson. COMPUTERS AND INTRACTABILITY: A Guide to the Theory of NP-Completeness. W. H. Freeman and co., 1979."},{"key":"16_CR7","unstructured":"M.M. Halld\u00f3rsson. Approximations via partitioning. Technical report, Japan Advanced Inst. of Sci. and Tech., March 1995."},{"key":"16_CR8","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1016\/0166-218X(83)90080-X","volume":"6","author":"D.S. Hochbaum","year":"1983","unstructured":"D.S. Hochbaum. Efficient bounds for the stable set, vertex cover and set packing problems. Discrete Applied Mathematics, 6:243\u2013254, 1983.","journal-title":"Discrete Applied Mathematics"},{"key":"16_CR9","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of Computer Computations","author":"R.M. Karp","year":"1972","unstructured":"R.M. Karp. Reducibility among combinatorial problems. In R. E. Miller and J. W. Thatcher, editors, Complexity of Computer Computations, pages 85\u2013103. Plenum Press, New York, 1972."},{"key":"16_CR10","unstructured":"L. Lov\u00e1sz and M.D. Plummer. Matching Theory. North-Holland, 1986."},{"key":"16_CR11","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1016\/0022-0000(80)90060-4","volume":"20","author":"J.M. Lewis","year":"1980","unstructured":"J.M. Lewis and M. Yannakakis. The Node-deletion problem for hereditary properties is NP-complete. Journal of Computer and System Sciences, 20:219\u2013230, 1980.","journal-title":"Journal of Computer and System Sciences"},{"key":"16_CR12","doi-asserted-by":"crossref","unstructured":"C. Lund and M. Yannakakis. The approximation of maximum subgraph problems. In Proc. of 20th International Colloquium on Automata, Languages and Programming, pages 40\u201351, 1993.","DOI":"10.1007\/3-540-56939-1_60"},{"key":"16_CR13","unstructured":"B. Monien and R. Schulz. Four approximation algorithms for the feedback vertex set problem. In Proc. of the 7th Conference on Graph Theoretic Concepts of Computer Science, pages 315\u2013326, 1981."},{"key":"16_CR14","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1007\/BF00290149","volume":"22","author":"B. Monien","year":"1985","unstructured":"B. Monien and E. Speckenmeyer. Ramsey numbers and an approximation algorithm for the vertex cover problem. Acta Informatica, 22:115\u2013123, 1985.","journal-title":"Acta Informatica"},{"key":"16_CR15","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"C. Papadimitriou","year":"1991","unstructured":"C. Papadimitriou and M. Yannakakis. Optimization, approximation and complexity classes. Journal of Computer and System Sciences, 43:425\u2013440, 1991.","journal-title":"Journal of Computer and System Sciences"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computations"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0015417","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,8]],"date-time":"2020-01-08T23:29:53Z","timestamp":1578526193000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0015417"}},"subtitle":["Extended abstract"],"short-title":[],"issued":{"date-parts":[[1995]]},"ISBN":["9783540605737","9783540477662"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/bfb0015417","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1995]]},"assertion":[{"value":"9 June 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}