{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,26]],"date-time":"2026-03-26T20:31:38Z","timestamp":1774557098549,"version":"3.50.1"},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[1992,6,1]],"date-time":"1992-06-01T00:00:00Z","timestamp":707356800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["BIT"],"published-print":{"date-parts":[[1992,6]]},"DOI":"10.1007\/bf01994876","type":"journal-article","created":{"date-parts":[[2005,8,4]],"date-time":"2005-08-04T20:22:09Z","timestamp":1123186929000},"page":"180-196","source":"Crossref","is-referenced-by-count":248,"title":["Approximating maximum independent sets by excluding subgraphs"],"prefix":"10.1007","volume":"32","author":[{"given":"Ravi","family":"Boppana","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Magn\u00fas M.","family":"Halld\u00f3rsson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"BF01994876_CR1","doi-asserted-by":"crossref","first-page":"354","DOI":"10.1016\/0097-3165(80)90030-8","volume":"29","author":"M. Ajtai","year":"1980","unstructured":"M. Ajtai, J. Koml\u00f3s, and E. Szemer\u00e9di.A note on Ramsey numbers. J. Combin. Theory Ser A, 29: 354\u2013360, 1980.","journal-title":"J. Combin. Theory Ser A"},{"key":"BF01994876_CR2","unstructured":"S. Arora and S. Safra.Approximating clique is NP-complete. Manuscript."},{"key":"BF01994876_CR3","unstructured":"R. Bar-Yehuda and S. Even.A 2 \u2014 loglogn\/2 logn performance ratio for the weighted vertex cover problem. Technical Report #260, Technion, Haifa, Jan. 1983."},{"issue":"4","key":"BF01994876_CR4","doi-asserted-by":"crossref","first-page":"459","DOI":"10.1007\/BF01840398","volume":"5","author":"B. Berger","year":"1990","unstructured":"B. Berger and J. Rompel.A better performance guarantee for approximate graph coloring. Algorithmica, 5 (4): 459\u2013466, 1990.","journal-title":"Algorithmica"},{"issue":"1","key":"BF01994876_CR5","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1016\/0890-5401(92)90056-L","volume":"96","author":"P. Berman","year":"1992","unstructured":"P. Berman and G. Schnitger.On the complexity of approximating the independent set problem. Information and Computation, 96 (1): 77\u201394, Jan. 1992.","journal-title":"Information and Computation"},{"key":"BF01994876_CR6","doi-asserted-by":"crossref","unstructured":"A. Blum.An O (n 4)approximation algorithm for 3-coloring. In Proc. 22nd Ann. ACM Symp. on Theory of Computing, pages 535\u2013542, 1989. Submitted to J. ACM.","DOI":"10.1145\/73007.73058"},{"key":"BF01994876_CR7","doi-asserted-by":"crossref","unstructured":"A. Blum.Some tools for approximate 3-coloring. In Proc. 31st Ann. IEEE Symp. on Found. of Comp. Sci., pages 554\u2013562, Oct. 1990.","DOI":"10.1109\/FSCS.1990.89576"},{"key":"BF01994876_CR8","unstructured":"B. Bollob\u00e1s.Random Graphs. Academic Press, 1985."},{"key":"BF01994876_CR9","doi-asserted-by":"crossref","unstructured":"R. B. Boppana and M. M. Halld\u00f3rsson.Approximating maximum independent sets by excluding subgraphs. In Proc. of 2nd Scand. Workshop on Algorithm Theory. Lecture Notes in Computer Science #447, pages 13\u201325. Springer-Verlag, July 1990.","DOI":"10.1007\/3-540-52846-6_74"},{"key":"BF01994876_CR10","doi-asserted-by":"crossref","unstructured":"V. Chv\u00e1tal.Determining the stability number of a graph. SIAM J. Comput., 6 (4), Dec. 1977.","DOI":"10.1137\/0206046"},{"key":"BF01994876_CR11","doi-asserted-by":"crossref","first-page":"253","DOI":"10.4064\/cm-16-1-253-256","volume":"16","author":"P. Erd\u00f6s","year":"1967","unstructured":"P. Erd\u00f6s.Some remarks on chromatic graphs. Colloq. Math., 16: 253\u2013256, 1967.","journal-title":"Colloq. Math."},{"key":"BF01994876_CR12","first-page":"463","volume":"2","author":"P. Erd\u00f6s","year":"1935","unstructured":"P. Erd\u00f6s and G. Szekeres.A combinatorial problem in geometry. Compositio Math., 2: 463\u2013470, 1935.","journal-title":"Compositio Math."},{"key":"BF01994876_CR13","doi-asserted-by":"crossref","unstructured":"U. Feige, S. Goldwasser, L. Lov\u00e1sz, S. Safra and M. Szegedy.Approximating clique is almost NP-complete. In Proc. 32nd Ann. IEEE Symp. on Found. of Comp. Sci., pp. 2\u201312, Oct. 1991.","DOI":"10.1109\/SFCS.1991.185341"},{"key":"BF01994876_CR14","first-page":"165","volume":"8","author":"T. Gallai","year":"1963","unstructured":"T. Gallai.Kritische graphen I. Publ. Math. Inst. Hungar. Acad. Sci., 8: 165\u2013192, 1963. (See Bollob\u00e1s, B.Extremal Graph Theory., Academic Press, 1978, page 285).","journal-title":"Publ. Math. Inst. Hungar. Acad. Sci."},{"key":"BF01994876_CR15","unstructured":"M. R. Garey and D. S. Johnson.Computers and Intractability: A Guide to the Theory of NP-completeness. Freeman, 1979."},{"key":"BF01994876_CR16","unstructured":"M. M. Halld\u00f3rsson.A still better performance guarantee for approximate graph coloring. Technical Report 90-44, DIMACS, June 1990."},{"key":"BF01994876_CR17","unstructured":"D. S. Johnson.Worst case behaviour of graph coloring algorithms. In Proc. 5th Southeastern Conf. on Combinatorics, Graph Theory, and Computing. Congressus Numerantium X, pages 513\u2013527, 1974."},{"key":"BF01994876_CR18","doi-asserted-by":"crossref","unstructured":"N. Linial and U. Vazirani.Graph products and chromatic numbers. In Proc. 30th Ann. IEEE Symp. on Found. of Comp. Sci., pages 124\u2013128, 1989.","DOI":"10.1109\/SFCS.1989.63466"},{"key":"BF01994876_CR19","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 Inf., 22: 115\u2013123, 1985.","journal-title":"Acta Inf."},{"key":"BF01994876_CR20","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1016\/0012-365X(83)90273-X","volume":"46","author":"J. B. Shearer","year":"1983","unstructured":"J. B. Shearer.A note on the independence number of triangle-free graphs. Discrete Math., 46: 83\u201387, 1983.","journal-title":"Discrete Math."},{"issue":"4","key":"BF01994876_CR21","doi-asserted-by":"crossref","first-page":"729","DOI":"10.1145\/2157.2158","volume":"30","author":"A. Wigderson","year":"1983","unstructured":"A. Wigderson.Improving the performance guarantee for approximate graph coloring. J. ACM, 30 (4): 729\u2013735, 1983.","journal-title":"J. ACM"},{"key":"BF01994876_CR22","unstructured":"S. Arora, C. Lund, R. Motwani, M. Sudan and M. Szegedy.On the intractability of approximation problems. Manuscript."}],"container-title":["BIT"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01994876.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01994876\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01994876","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,3]],"date-time":"2025-01-03T02:19:53Z","timestamp":1735870793000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01994876"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1992,6]]},"references-count":22,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1992,6]]}},"alternative-id":["BF01994876"],"URL":"https:\/\/doi.org\/10.1007\/bf01994876","relation":{},"ISSN":["0006-3835","1572-9125"],"issn-type":[{"value":"0006-3835","type":"print"},{"value":"1572-9125","type":"electronic"}],"subject":[],"published":{"date-parts":[[1992,6]]}}}