{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,30]],"date-time":"2026-04-30T03:35:11Z","timestamp":1777520111834,"version":"3.51.4"},"reference-count":15,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[1985,4,1]],"date-time":"1985-04-01T00:00:00Z","timestamp":481161600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Acta Informatica"],"published-print":{"date-parts":[[1985,4]]},"DOI":"10.1007\/bf00290149","type":"journal-article","created":{"date-parts":[[2004,10,5]],"date-time":"2004-10-05T05:53:34Z","timestamp":1096955614000},"page":"115-123","source":"Crossref","is-referenced-by-count":119,"title":["Ramsey numbers and an approximation algorithm for the vertex cover problem"],"prefix":"10.1007","volume":"22","author":[{"given":"Burkhard","family":"Monien","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ewald","family":"Speckenmeyer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"CR1","doi-asserted-by":"crossref","first-page":"354","DOI":"10.1016\/0097-3165(80)90030-8","volume":"29","author":"M. Ajtai","year":"1980","unstructured":"Ajtai, M., Koml\u00f3s, J., Szemeredi, E.: A note on Ramsey numbers. J. Comb. Theory, Ser. A 29, 354?360 (1980)","journal-title":"J. Comb. Theory, Ser. A"},{"key":"CR2","doi-asserted-by":"crossref","unstructured":"Bar-Yehuda, R., Even, S.: On approximating a vertex cover for planar graphs. Proc. 14th Ann. ACM Symp. Th. Computing, pp. 303?309. San Francisco 1982","DOI":"10.1145\/800070.802205"},{"key":"CR3","unstructured":"Bar-Yehuda, R, Even, S.: A 2?log logn\/2logn performance ratio for the weighted vertex cover problem. Technion Haifa, Technical Report #260, January 1983"},{"key":"CR4","doi-asserted-by":"crossref","first-page":"34","DOI":"10.4153\/CJM-1959-003-9","volume":"11","author":"P. Erd\u00f6s","year":"1959","unstructured":"Erd\u00f6s, P.: Graph theory and probability, Can. J. Math. 11, 34?38 (1959)","journal-title":"Can. J. Math."},{"key":"CR5","unstructured":"Erd\u00f6s, P., Gallai, T.: On the minimal number of vertices representing the edges of a graph, pp. 181?203. Magyar Tudom\u00e1nyos Akad\u00e9mia Matematikai Kutato Int\u00e9zet\u00e9nek K\u00f6zlem\u00e9nyei VI. Evfolyam 1961"},{"key":"CR6","volume-title":"Graph algorithms","author":"S. Even","year":"1979","unstructured":"Even, S.: Graph algorithms. Rockville, MD: Computer Science Press 1979"},{"key":"CR7","unstructured":"Fajtlowicz, S.: On the size of independent sets in graphs. In: Proc. 9th S.E. Conf. Combinatorics, Graph Theory and Computing, Boca Raton, Congressum Numerantium No. XXI, pp. 269?274. Utilitas Mathematical-Publ. Inc. 1978"},{"key":"CR8","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1016\/S0021-9800(68)80038-9","volume":"4","author":"J.E Graver","year":"1968","unstructured":"Graver, J.E, Yackel, J.: Some graph theoretic results with Ramsey's theorem. J. Comb. Theory, Ser. A 4, 125?175 (1968)","journal-title":"J. Comb. Theory, Ser. A"},{"key":"CR9","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1016\/0095-8956(83)90003-5","volume":"34","author":"J.R. Griggs","year":"1983","unstructured":"Griggs, J.R.: Lower bounds on the independence number in terms of the degrees. J. Comb. Theory, Ser. B 34, 22?39 (1983)","journal-title":"J. Comb. Theory, Ser. B"},{"key":"CR10","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1016\/0166-218X(83)90080-X","volume":"6","author":"D.S. Hochbaum","year":"1983","unstructured":"Hochbaum, D.S.: Efficient bounds for the stable set, vertex cover and set packing problems. Discrete Appl. Math. 6, 243?254 (1983)","journal-title":"Discrete Appl. Math."},{"key":"CR11","doi-asserted-by":"crossref","first-page":"179","DOI":"10.4153\/CMB-1982-024-9","volume":"25","author":"G. Hopkins","year":"1982","unstructured":"Hopkins, G., Staton, W.: Girth and independence ratio. Can. Math. Bull. 25, 179?186 (1982)","journal-title":"Can. Math. Bull."},{"key":"CR12","volume-title":"Theorie der endlichen und unendlichen Graphen","author":"D. K\u00f6nig","year":"1936","unstructured":"K\u00f6nig, D.: Theorie der endlichen und unendlichen Graphen. Leipzig: Akademische Verlagsgesellschaft 1936"},{"key":"CR13","doi-asserted-by":"crossref","first-page":"355","DOI":"10.1007\/BF02251238","volume":"31","author":"B. Monien","year":"1983","unstructured":"Monien, B.: The complexity of determining a shortest cycle of even length. Computing 31, 355?369 (1983)","journal-title":"Computing"},{"key":"CR14","doi-asserted-by":"crossref","unstructured":"Monien, B., Speckenmeyer, E.: Some further approximation algorithms for the vertex cover problem. In: Proc. 8th Coll. on Trees in Algebra and Programming (CAAP 83), L'Aquila. Lecture Notes in Computer Science 159, 341?349 (1983)","DOI":"10.1007\/3-540-12727-5_21"},{"key":"CR15","doi-asserted-by":"crossref","first-page":"232","DOI":"10.1007\/BF01580444","volume":"8","author":"G.L. Nemhauser","year":"1975","unstructured":"Nemhauser, G.L., Trotter, L.E.: Vertex packing: structural properties and algorithms. Math. Program. 8, 232?248 (1975)","journal-title":"Math. Program."}],"container-title":["Acta Informatica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF00290149.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF00290149\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF00290149","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,8]],"date-time":"2019-04-08T21:15:19Z","timestamp":1554758119000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF00290149"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1985,4]]},"references-count":15,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1985,4]]}},"alternative-id":["BF00290149"],"URL":"https:\/\/doi.org\/10.1007\/bf00290149","relation":{},"ISSN":["0001-5903","1432-0525"],"issn-type":[{"value":"0001-5903","type":"print"},{"value":"1432-0525","type":"electronic"}],"subject":[],"published":{"date-parts":[[1985,4]]}}}