{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,30]],"date-time":"2025-06-30T11:27:19Z","timestamp":1751282839462},"publisher-location":"Berlin, Heidelberg","reference-count":9,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540605737"},{"type":"electronic","value":"9783540477662"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1995]]},"DOI":"10.1007\/bfb0015418","type":"book-chapter","created":{"date-parts":[[2005,11,13]],"date-time":"2005-11-13T06:50:06Z","timestamp":1131864606000},"page":"152-161","source":"Crossref","is-referenced-by-count":9,"title":["Greedy approximations of independent sets in low degree graphs"],"prefix":"10.1007","author":[{"given":"Magn\u00fas M.","family":"Halld\u00f3rsson","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kiyohito","family":"Yoshihara","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,9]]},"reference":[{"key":"17_CR1","doi-asserted-by":"crossref","unstructured":"S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy. Proof verification and hardness of approximation problems. FOCS 1992.","DOI":"10.1109\/SFCS.1992.267823"},{"key":"17_CR2","doi-asserted-by":"crossref","unstructured":"P. Berman and T. Fujito. On the approximation properties of independent set problem in degree 3 graphs. WADS 1995.","DOI":"10.1007\/3-540-60220-8_84"},{"key":"17_CR3","unstructured":"P. Berman and M. F\u00fcrer. Approximating maximum independent set in bounded degree graphs. SODA 1994."},{"key":"17_CR4","unstructured":"M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-completeness. Freeman, 1979."},{"key":"17_CR5","unstructured":"M. M. Halld\u00f3rsson. Approximating discrete collections via local improvements. SODA 1995."},{"key":"17_CR6","doi-asserted-by":"crossref","unstructured":"M. M. Halld\u00f3rsson and J. Radhakrishnan. Greed is good: Approximating independent sets in sparse and bounded-degree graphs. STOC 1994. To appear in Algorithmica.","DOI":"10.1145\/195058.195221"},{"key":"17_CR7","doi-asserted-by":"crossref","unstructured":"M. M. Halld\u00f3rsson and J. Radhakrishnan. Improved approximations of independent sets in bounded-degree graphs. SWAT 1994.","DOI":"10.1007\/3-540-58218-5_18"},{"issue":"4","key":"17_CR8","first-page":"475","volume":"1","author":"M. M. Halld\u00f3rsson","year":"1994","unstructured":"M. M. Halld\u00f3rsson and J. Radhakrishnan. Improved approximations of independent sets in bounded-degree via subgraph removal. Nordic J. Computing, 1(4):475\u2013492, 1994.","journal-title":"Nordic J. Computing"},{"key":"17_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."}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computations"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0015418","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,10]],"date-time":"2020-04-10T20:49:36Z","timestamp":1586551776000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0015418"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995]]},"ISBN":["9783540605737","9783540477662"],"references-count":9,"URL":"https:\/\/doi.org\/10.1007\/bfb0015418","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1995]]}}}