{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T01:48:13Z","timestamp":1725587293721},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642220050"},{"type":"electronic","value":"9783642220067"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-22006-7_41","type":"book-chapter","created":{"date-parts":[[2011,6,20]],"date-time":"2011-06-20T07:44:05Z","timestamp":1308555845000},"page":"486-497","source":"Crossref","is-referenced-by-count":1,"title":["Recoverable Values for Independent Sets"],"prefix":"10.1007","author":[{"given":"Uriel","family":"Feige","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daniel","family":"Reichman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"41_CR1","doi-asserted-by":"publisher","DOI":"10.1002\/9780470277331","volume-title":"The Probablistic Method","author":"N. Alon","year":"2008","unstructured":"Alon, N., Spencer, J.: The Probablistic Method. Wiley, Chichester (2008)"},{"key":"41_CR2","doi-asserted-by":"crossref","unstructured":"Austrin, P., Khot, S., Safra, S.: Inapproximability of vertex cover and independent set in bounded degree graphs. In: CCC (2009)","DOI":"10.1109\/CCC.2009.38"},{"key":"41_CR3","unstructured":"Berman, P., Fujito, T.: On approximation properties of the independent set problem for low degree graphs. Theory of Computing Systems"},{"key":"41_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1007\/978-3-540-27796-5_5","volume-title":"Structural Information and Communication Complexity","author":"M. Chleb\u00edk","year":"2004","unstructured":"Chleb\u00edk, M., Chleb\u00edkov\u00e1, J.: On approximability of the independent set problem for low degree graphs. In: Kralovic, R., S\u00fdkora, O. (eds.) SIROCCO 2004. LNCS, vol.\u00a03104, pp. 47\u201356. Springer, Heidelberg (2004)"},{"key":"41_CR5","series-title":"Lecture Notes in Computer Science","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"U. Feige","year":"2010","unstructured":"Feige, U., Immorlica, N., Mirrokni, V.S., Nazerzadeh, H.: Pass approximation. In: Serna, M., Shaltiel, R., Jansen, K., Rolim, J. (eds.) APPROX 2010, LNCS, vol.\u00a06302. Springer, Heidelberg (2010)"},{"key":"41_CR6","unstructured":"Feige, U., Reichman, D.: Recoverable values for independent sets (Detailed version of current paper), \n                    \n                      http:\/\/www.arxiv.org\/PS_cache\/arxiv\/pdf\/1103\/1103.5609v1.pdf"},{"issue":"1","key":"41_CR7","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1016\/0095-8956(83)90003-5","volume":"34","author":"J. Griggs","year":"1983","unstructured":"Griggs, J.: Lower bounds on the independence number in terms of the degrees. Journal of Combinatorial Theory, Series B\u00a034(1), 22\u201339 (1983)","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"41_CR8","doi-asserted-by":"crossref","unstructured":"Guruswami, V., Kemal Sinop, A.: The complexity of finding independent sets in bounded degree (hyper)graphs of low chromatic number. In: SODA (2011)","DOI":"10.1137\/1.9781611973082.125"},{"key":"41_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"360","DOI":"10.1007\/978-3-642-14165-2_31","volume-title":"Automata, Languages and Programming","author":"V. Guruswami","year":"2010","unstructured":"Guruswami, V., Saket, R.: On the inapproximability of vertex cover on k-partite k-uniform hypergraphs. In: Abramsky, S., Gavoille, C., Kirchner, C., Meyer auf der Heide, F., Spirakis, P.G. (eds.) ICALP 2010. LNCS, vol.\u00a06198, pp. 360\u2013371. Springer, Heidelberg (2010)"},{"key":"41_CR10","doi-asserted-by":"publisher","first-page":"1","DOI":"10.7155\/jgaa.00020","volume":"4","author":"M.M. Halldorsson","year":"2000","unstructured":"Halldorsson, M.M.: Approximations of weighted independent set and hereditary subset problems. Journal of Graph Algorithms and Applications\u00a04, 1\u201316 (2000)","journal-title":"Journal of Graph Algorithms and Applications"},{"key":"41_CR11","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1007\/BF02523693","volume":"18","author":"M.M. Halldorsson","year":"1997","unstructured":"Halldorsson, M.M., Radhakrishnan, J.: Greed is good: Approximating independent sets in sparse and bounded-degree graphs. Algorithmica\u00a018, 145\u2013163 (1997)","journal-title":"Algorithmica"},{"key":"41_CR12","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1007\/BF02392825","volume":"182","author":"J. Hastad","year":"1999","unstructured":"Hastad, J.: Clique is hard to approximate within n\n                           1\u2009\u2212\u2009\u03b5\n                           . Acta Mathematica\u00a0182, 105\u2013142 (1999)","journal-title":"Acta Mathematica"},{"key":"41_CR13","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1016\/0166-218X(83)90080-X","volume":"6","author":"D. Hochbaum","year":"1983","unstructured":"Hochbaum, D.: Efficient bounds for the stable set, vertex cover, and set packing problems. Discrete Appl. Math\u00a06, 243\u2013254 (1983)","journal-title":"Discrete Appl. Math"},{"key":"41_CR14","doi-asserted-by":"crossref","unstructured":"Khot, S., Regev, O.: Vertex cover might be hard to approximate to within 2\u2009\u2212\u2009\u03b5. In: CCC (2003)","DOI":"10.1109\/CCC.2003.1214437"},{"key":"41_CR15","doi-asserted-by":"publisher","first-page":"232","DOI":"10.1007\/BF01580444","volume":"8","author":"G. Nemhauser","year":"1975","unstructured":"Nemhauser, G., Trotter, L.: Vertex packings: Structural properties and algorithms. Math. Programming\u00a08, 232\u2013248 (1975)","journal-title":"Math. Programming"},{"key":"41_CR16","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1016\/S0166-218X(02)00205-6","volume":"126","author":"M. Sakai","year":"1999","unstructured":"Sakai, M., Togasaki, M., Yamazaki, K.: A note on greedy algorithms for the maximum weighted independent set problem. Discrete Applied Mathematics\u00a0126, 313\u2013322 (1999)","journal-title":"Discrete Applied Mathematics"},{"key":"41_CR17","unstructured":"Wei, V.K.: A lower bound on the stability number of a simple graph. Bell Laboratories Technical Memorandum 8 I- I 12 17.9 (1981)"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-22006-7_41","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,29]],"date-time":"2019-03-29T06:56:14Z","timestamp":1553842574000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-22006-7_41"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642220050","9783642220067"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-22006-7_41","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}