{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:55:00Z","timestamp":1725663300241},"publisher-location":"Berlin, Heidelberg","reference-count":11,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540127277"},{"type":"electronic","value":"9783540387145"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1983]]},"DOI":"10.1007\/3-540-12727-5_21","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T17:55:01Z","timestamp":1330192501000},"page":"341-349","source":"Crossref","is-referenced-by-count":10,"title":["Some further approximation algorithms for the vertex cover problem"],"prefix":"10.1007","author":[{"given":"B.","family":"Monien","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"E.","family":"Speckenmeyer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,5,29]]},"reference":[{"key":"21_CR1","doi-asserted-by":"publisher","first-page":"198","DOI":"10.1016\/0196-6774(81)90020-1","volume":"2","author":"R. Bar-Yehuda","year":"1982","unstructured":"R. Bar-Yehuda and S. Even: A linear-time approximation algorithm for the weighted vertex cover problem, J. Algorithms 2 (1982), 198\u2013203","journal-title":"J. Algorithms"},{"key":"21_CR2","doi-asserted-by":"crossref","unstructured":"R. Bar-Yehuda and S. Even: On Approximating a Vertex Cover for Planar Graphs, Proc. 14th Annual ACM Symposium on Theory of Comuting (1982), 303\u2013309","DOI":"10.1145\/800070.802205"},{"key":"21_CR3","unstructured":"P. Erd\u00f6s and T. Gallai: ON THE MINIMAL NUMBER OF VERTICES REPRESENTING THE EDGES OF A GRAPH, MAGYAR TUDOM\u00c1NYOS AKAD\u00c9MIA MATEMATIKAI KUTATO INT\u00c9ZET\u00c9NEK K\u00d6ZLEM\u00c9NYEI VI. EVFOLYAM 1961, 181\u2013203"},{"key":"21_CR4","unstructured":"S. Fajtlowicz: On the size of independent sets in graphs, Proc. 9th S.E. Conf. Combinatorics, Graph Theory and Computing (1978), 269\u2013274"},{"key":"21_CR5","unstructured":"D. Hochbaum: Efficient Bounds for the Stable Set, Vertex Cover and Set Packing Problems, W.P. # 50-80-81, GSIA, Carnegie-Mellon University, May 1981"},{"key":"21_CR6","doi-asserted-by":"crossref","first-page":"179","DOI":"10.4153\/CMB-1982-024-9","volume":"25","author":"G. Hopkins","year":"1982","unstructured":"G. Hopkins and W. Staton: Girth and Independence Ratio, Canad. Math. Bull. 25 (1982), 179\u2013186","journal-title":"Canad. Math. Bull."},{"key":"21_CR7","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1137\/0202019","volume":"4","author":"J. E. Hopcroft","year":"1973","unstructured":"J.E. Hopcroft and R.M. Karp: An n5\/2 Algorithm for Maximal Matchings in Bipartite graphs, SIAM J. Comput. 4 (1973), 225\u2013231","journal-title":"SIAM J. Comput."},{"key":"21_CR8","unstructured":"D. K\u00f6nig: Theorie der endlichen und unendlichen Graphen, Leipzig, 1936"},{"key":"21_CR9","unstructured":"B. Monien: The Complexity of Determining a Shortest Cycle of even Length, Proc. Workshop \"Graphtheoretic Concepts in Computer Science, Hanser Verlag, 1982"},{"key":"21_CR10","doi-asserted-by":"publisher","first-page":"232","DOI":"10.1007\/BF01580444","volume":"8","author":"G. L. Nemhauser","year":"1975","unstructured":"G.L. Nemhauser and L.E. Trotter: Vertex Packings: Structural Properties and Algorithms, Mathematical Programming 8 (1975), 232\u2013248","journal-title":"Mathematical Programming"},{"key":"21_CR11","unstructured":"E. Speckenmeyer: Covering all circuits in undirected graphs of degree 3 by a minimal number of vertices, Technical Report, Universit\u00e4t Paderborn, 1982"}],"container-title":["Lecture Notes in Computer Science","CAAP'83"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-12727-5_21.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T20:50:54Z","timestamp":1619556654000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-12727-5_21"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1983]]},"ISBN":["9783540127277","9783540387145"],"references-count":11,"URL":"https:\/\/doi.org\/10.1007\/3-540-12727-5_21","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1983]]}}}