{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,9]],"date-time":"2025-07-09T22:46:51Z","timestamp":1752101211276},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540412557"},{"type":"electronic","value":"9783540409960"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2000]]},"DOI":"10.1007\/3-540-40996-3_12","type":"book-chapter","created":{"date-parts":[[2007,8,28]],"date-time":"2007-08-28T21:17:32Z","timestamp":1188335852000},"page":"132-143","source":"Crossref","is-referenced-by-count":4,"title":["On Approximating Minimum Vertex Cover for Graphs with Perfect Matching"],"prefix":"10.1007","author":[{"given":"Jianer","family":"Chen","sequence":"first","affiliation":[]},{"given":"Iyad A.","family":"Kanj","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2002,1,29]]},"reference":[{"key":"12_CR1","first-page":"27","volume":"25","author":"R. Bar-Yehuda","year":"1985","unstructured":"Bar-Yehuda, R. and Even, S.: A local-ratio theorem for approximating the weighted vertex cover problem. Annals of Discrete Mathematics 25 (1985) 27\u201346","journal-title":"Annals of Discrete Mathematics"},{"key":"12_CR2","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1007\/s002240000113","volume":"32","author":"P. Berman","year":"1999","unstructured":"Berman, P. and Fujito, T.: On approximation properties of the independent set problem for low degree graphs. Theory Comput. Systems 32 (1999) 115\u2013132","journal-title":"Theory Comput. Systems"},{"key":"12_CR3","unstructured":"Chen, J.: Introduction to Tractability and Approximability of Optimization problems Lecture Notes, Department of Computer Science, Texas A&M University (2000)"},{"key":"12_CR4","doi-asserted-by":"crossref","unstructured":"Chen, J. and Kanj, I. A.: On approximating minimum vertex cover for graphs with perfect matching, Tech. Report, Department of Computer Science, Texas A&M University (2000)","DOI":"10.1007\/3-540-40996-3_12"},{"key":"12_CR5","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1016\/S0304-3975(97)00226-0","volume":"225","author":"A. Clementi","year":"1999","unstructured":"Clementi, A. and Trevisan, L.: Improved non-approximability results for minimum vertex cover with density constraints. Theoretical Computer Science 225 (1999) 113\u2013128","journal-title":"Theoretical Computer Science"},{"key":"12_CR6","doi-asserted-by":"crossref","unstructured":"Feige, U., and Goemans, M.: Approximating the value of two prover proof system, with applications to MAX-2SAT and MAX-DCUT. Proc. 3rd Israel Symp. on Theory of Computing and Systems (1995) 182\u2013189","DOI":"10.1109\/ISTCS.1995.377033"},{"key":"12_CR7","volume-title":"Computers and Intractability: A Guide to the Theory of NP-completeness","author":"M. Garey","year":"1979","unstructured":"Garey, M. and Johnson, D.: Computers and Intractability: A Guide to the Theory of NP-completeness. Freeman, San Francisco, (1979)"},{"key":"12_CR8","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/0304-3975(76)90059-1","volume":"1","author":"M. Garey","year":"1976","unstructured":"Garey, M., Johnson, D., and Stockmeyer, L. J.: Some simplified NP-complete graph problems, Theoretical Computer Science 1 (1976) 237\u2013267","journal-title":"Theoretical Computer Science"},{"key":"12_CR9","unstructured":"Halld\u00f3rsson, M.: Approximating discrete collections via local improvements. Proc. 6th Ann ACM-SIAM Symp. on Discrete Algorithms (1995) 160\u2013169"},{"key":"12_CR10","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1007\/BF02523693","volume":"18","author":"M. Halld\u00f3rsson","year":"1997","unstructured":"Halld\u00f3rsson, M. and Radhakrishnan, J.: Greed is good: approximating independent sets in sparse and bounded-degree graphs. Algorithmica 18 (1997) 145\u2013163","journal-title":"Algorithmica"},{"key":"12_CR11","unstructured":"Halperin, E.: Improved approximation algorithms for the vertex cover problem in graphs and hypergraphs. Proc. 11th Ann ACM-SIAM Symp. on Discrete Algorithms (2000) 329\u2013337"},{"key":"12_CR12","unstructured":"H\u00e5stad, J.: Some optimal inapproximability results. Proc. 28th Annual ACM Symposium on Theory of Computing (1997) 1\u201310"},{"key":"12_CR13","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1016\/0166-218X(83)90080-X","volume":"6","author":"D. Hochbaum","year":"1983","unstructured":"Hochbaum, D.: Efficient bounds for the stable set, vertex cover and set packing problems. Discrete Applied Mathematics 6. (1983) 243\u2013254","journal-title":"Discrete Applied Mathematics"},{"key":"12_CR14","first-page":"94","volume-title":"Approximation Algorithms for NP-hard Problems","author":"D. Hochbaum","year":"1997","unstructured":"Hochbaum, D.: Approximating covering and packing problems: set cover, vertex cover, independent set, and related problems In: Hochbaum, D. (ed.): Approximation Algorithms for NP-hard Problems. PWS Publishing Company, Boston (1997) 94\u2013143"},{"key":"12_CR15","unstructured":"Karloff, H. and Zwick, U.: A 7=8-approximation algorithm for MAX-SAT? Proc. 38th IEEE Symposium on the Foundation of Computer Science (1997) 406\u2013415"},{"key":"12_CR16","unstructured":"Micali, S. and Vazirani, V.: An O(\u221a\u231dV\u231d. \u231dE\u231d) algorithm for finding maximum matching in general graphs, Proc. 21st IEEE Symposium on the Foundation of Computer Science (1980) 17\u201327"},{"key":"12_CR17","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1007\/BF00290149","volume":"22","author":"B. Monien","year":"1985","unstructured":"Monien, B. and Speckenmeyer, E.: Ramsey numbers and an approximation algorithm for the vertex cover problem. Acta Informatica 22 (1985) 115\u2013123","journal-title":"Acta Informatica"},{"key":"12_CR18","doi-asserted-by":"publisher","first-page":"232","DOI":"10.1007\/BF01580444","volume":"8","author":"G. L. Nemhauser","year":"1975","unstructured":"Nemhauser, G. L. and Trotter, L. E.: Vertex packing: structural properties and algorithms. Mathematical Programming 8 (1975) 232\u2013248","journal-title":"Mathematical Programming"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-40996-3_12","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,2]],"date-time":"2019-05-02T13:25:58Z","timestamp":1556803558000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-40996-3_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9783540412557","9783540409960"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/3-540-40996-3_12","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2000]]}}}