{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,9]],"date-time":"2025-07-09T23:00:40Z","timestamp":1752102040341},"publisher-location":"Berlin, Heidelberg","reference-count":13,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642452772"},{"type":"electronic","value":"9783642452789"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-45278-9_39","type":"book-chapter","created":{"date-parts":[[2013,11,25]],"date-time":"2013-11-25T15:35:18Z","timestamp":1385393718000},"page":"438-442","source":"Crossref","is-referenced-by-count":4,"title":["New Approximation Algorithms for the Vertex Cover Problem"],"prefix":"10.1007","author":[{"given":"Franc\u0328ois","family":"Delbot","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christian","family":"Laforest","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Raksmey","family":"Phan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"1","key":"39_CR1","first-page":"56","volume":"6","author":"E. Angel","year":"2011","unstructured":"Angel, E., Campigotto, R., Laforest, C.: Analysis and comparison of three algorithms for the vertex cover problem on large graphs with low memory capacities. Algorithmic Operations Research\u00a06(1), 56\u201367 (2011)","journal-title":"Algorithmic Operations Research"},{"key":"39_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1007\/978-3-642-30850-5_5","volume-title":"Experimental Algorithms","author":"E. Angel","year":"2012","unstructured":"Angel, E., Campigotto, R., Laforest, C.: Implementation and comparison of heuristics for the vertex cover problem on huge graphs. In: Klasing, R. (ed.) SEA 2012. LNCS, vol.\u00a07276, pp. 39\u201350. Springer, Heidelberg (2012)"},{"key":"39_CR3","first-page":"27","volume":"25","author":"R. Bar-Yehuda","year":"1985","unstructured":"Bar-Yehuda, R., Even, S.: A local ratio theorem for approximating the weighted vertex cover problem. Annals of Discrete Mathematics\u00a025, 27\u201345 (1985)","journal-title":"Annals of Discrete Mathematics"},{"issue":"9","key":"39_CR4","doi-asserted-by":"publisher","first-page":"436","DOI":"10.1016\/j.ipl.2008.12.021","volume":"109","author":"E. Birmel\u00e9","year":"2009","unstructured":"Birmel\u00e9, E., Delbot, F., Laforest, C.: Mean analysis of an online algorithm for the vertex cover problem. Information Processing Letters\u00a0109(9), 436\u2013439 (2009)","journal-title":"Information Processing Letters"},{"issue":"3-4","key":"39_CR5","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1016\/j.ipl.2008.02.004","volume":"107","author":"F. Delbot","year":"2008","unstructured":"Delbot, F., Laforest, C.: A better list heuristic for vertex cover. Information Processing Letters\u00a0107(3-4), 125\u2013127 (2008)","journal-title":"Information Processing Letters"},{"key":"39_CR6","doi-asserted-by":"crossref","unstructured":"Delbot, F., Laforest, C.: Analytical and experimental comparison of six algorithms for the vertex cover problem. ACM Journal of Experimental Algorithmics 15, 1.4:1.1\u20131.4:1.27 (2010)","DOI":"10.1145\/1671970.1865971"},{"key":"39_CR7","doi-asserted-by":"crossref","unstructured":"Delbot, F., Laforest, C., Phan, R.: New approximation algorithms for the vertex cover problem and variants. Research Report RR-13-02, LIMOS, Clermont Ferrand, France (2013)","DOI":"10.1007\/978-3-642-45278-9_39"},{"key":"39_CR8","doi-asserted-by":"crossref","unstructured":"H\u00e5stad, J.: Some optimal inapproximability results. In: STOC, pp. 1\u201310 (1997)","DOI":"10.1145\/258533.258536"},{"key":"39_CR9","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1597036.1597045","volume":"5","author":"G. Karakostas","year":"2009","unstructured":"Karakostas, G.: A better approximation ratio for the vertex cover problem. ACM Transactions on Algorithms 5, 41:1\u201341:8 (2009)","journal-title":"ACM Transactions on Algorithms"},{"issue":"3","key":"39_CR10","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1016\/j.jcss.2007.06.019","volume":"74","author":"S. Khot","year":"2008","unstructured":"Khot, S., Regev, O.: Vertex cover might be hard to approximate to within 2\u2009\u2212\u2009\u03b5. Journal of Computer and System Sciences\u00a074(3), 335\u2013349 (2008)","journal-title":"Journal of Computer and System Sciences"},{"key":"39_CR11","unstructured":"Papadimitriou, C.H., Steiglitz, K.: Combinatorial Optimization: Algorithms and Complexity. Prentice-Hall (1982)"},{"issue":"5","key":"39_CR12","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1016\/0020-0190(82)90022-9","volume":"14","author":"C. Savage","year":"1982","unstructured":"Savage, C.: Depth-first search and the vertex cover problem. Inf. Process. Lett.\u00a014(5), 233\u2013235 (1982)","journal-title":"Inf. Process. Lett."},{"key":"39_CR13","unstructured":"Vazirani, V.V.: Approximation algorithms. Springer (2001)"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-45278-9_39","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,4]],"date-time":"2019-08-04T01:50:22Z","timestamp":1564883422000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-45278-9_39"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642452772","9783642452789"],"references-count":13,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-45278-9_39","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}