{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,12]],"date-time":"2024-09-12T15:16:35Z","timestamp":1726154195795},"publisher-location":"Berlin, Heidelberg","reference-count":12,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540582182"},{"type":"electronic","value":"9783540485773"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1994]]},"DOI":"10.1007\/3-540-58218-5_18","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T15:36:57Z","timestamp":1330270617000},"page":"195-206","source":"Crossref","is-referenced-by-count":10,"title":["Improved approximations of independent sets in bounded-degree graphs"],"prefix":"10.1007","author":[{"given":"Magn\u00fas M.","family":"Halld\u00f3rsson","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jaikumar","family":"Radhakrishnan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,5,30]]},"reference":[{"issue":"4","key":"18_CR1","doi-asserted-by":"crossref","first-page":"313","DOI":"10.1007\/BF02579451","volume":"1","author":"M. Ajtai","year":"1981","unstructured":"M. Ajtai, P. Erd\u0151s, J. Koml\u00f3s, and E. Szemer\u00e9di. On Tur\u00e1n's theorem for sparse graphs. Combinatorica, 1(4):313\u2013317, 1981.","journal-title":"Combinatorica"},{"key":"18_CR2","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":"18_CR3","doi-asserted-by":"crossref","unstructured":"S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy. Proof verification and intractability of approximation problems. In Proc. 33nd IEEE Symp. on Found. of Comp. Sci., pages 14\u201323, Oct. 1992.","DOI":"10.1109\/SFCS.1992.267823"},{"key":"18_CR4","doi-asserted-by":"crossref","unstructured":"M. Bellare and M. Sudan. Improved non-approximability results. To appear in STOC '94, May 1994.","DOI":"10.1145\/195058.195129"},{"key":"18_CR5","unstructured":"P. Berman and M. Purer. Approximating maximum independent set in bounded degree graphs. In Proc. Fifth ACM-SIAM Symp. on Discrete Algorithms, Jan. 1994."},{"issue":"2","key":"18_CR6","doi-asserted-by":"crossref","first-page":"180","DOI":"10.1007\/BF01994876","volume":"32","author":"R. B. Boppana","year":"1992","unstructured":"R. B. Boppana and M. M. Halld\u00f3rsson. Approximating maximum independent sets by excluding subgraphs. BIT, 32(2):180\u2013196, June 1992.","journal-title":"BIT"},{"key":"18_CR7","doi-asserted-by":"crossref","first-page":"253","DOI":"10.4064\/cm-16-1-253-256","volume":"16","author":"P. Erd\u0151s","year":"1967","unstructured":"P. Erd\u0151s. Some remarks on chromatic graphs. Colloq. Math., 16:253\u2013256, 1967.","journal-title":"Colloq. Math."},{"key":"18_CR8","doi-asserted-by":"crossref","unstructured":"M. M. Halld\u00f3rsson and J. Radhakrishnan. Greed is good: Approximating independent sets in sparse and bounded-degree graphs. To appear in STOC '94, May 1994.","DOI":"10.1145\/195058.195221"},{"key":"18_CR9","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1016\/0166-218X(83)90080-X","volume":"6","author":"D. S. Hochbaum","year":"1983","unstructured":"D.S. Hochbaum. Efficient bounds for the stable set, vertex cover, and set packing problems. Disc. Applied Math., 6:243\u2013254, 1983.","journal-title":"Disc. Applied Math."},{"key":"18_CR10","unstructured":"S. Khanna, R. Motwani, M. Sudan, and U. Vazirani. On syntactic versus computation views of approximability. Manuscript, Dec. 1993."},{"key":"18_CR11","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"C. Papadimitriou","year":"1991","unstructured":"C. Papadimitriou and M. Yannakakis. Optimization, approximation, and complexity. J. Comput. Syst. Sci., 43:425\u2013440, 1991.","journal-title":"J. Comput. Syst. Sci."},{"key":"18_CR12","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."}],"container-title":["Lecture Notes in Computer Science","Algorithm Theory \u2014 SWAT '94"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-58218-5_18.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T21:18:46Z","timestamp":1605647926000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-58218-5_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994]]},"ISBN":["9783540582182","9783540485773"],"references-count":12,"URL":"https:\/\/doi.org\/10.1007\/3-540-58218-5_18","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1994]]}}}