{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:18:25Z","timestamp":1759637905879},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642163661"},{"type":"electronic","value":"9783642163678"}],"license":[{"start":{"date-parts":[[2010,1,1]],"date-time":"2010-01-01T00:00:00Z","timestamp":1262304000000},"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":[[2010]]},"DOI":"10.1007\/978-3-642-16367-8_14","type":"book-chapter","created":{"date-parts":[[2010,10,7]],"date-time":"2010-10-07T15:25:55Z","timestamp":1286465155000},"page":"234-239","source":"Crossref","is-referenced-by-count":10,"title":["On Constant Time Approximation of Parameters of Bounded Degree Graphs"],"prefix":"10.1007","author":[{"given":"Noga","family":"Alon","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"14_CR1","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1007\/BF02579451","volume":"1","author":"M. Ajtai","year":"1981","unstructured":"Ajtai, M., Erd\u00f6s, P., Koml\u00f3s, J., Szemer\u00e9di, E.: On Turan\u2019s theorem for sparse graphs. Combinatorica\u00a01, 313\u2013317 (1981)","journal-title":"Combinatorica"},{"key":"14_CR2","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1002\/(SICI)1098-2418(199610)9:3<271::AID-RSA1>3.0.CO;2-U","volume":"9","author":"N. Alon","year":"1996","unstructured":"Alon, N.: Independence numbers of locally sparse graphs and a Ramsey type problem. Random Structures and Algorithms\u00a09, 271\u2013278 (1996)","journal-title":"Random Structures and Algorithms"},{"key":"14_CR3","first-page":"253","volume":"80","author":"N. Alon","year":"1998","unstructured":"Alon, N., Kahale, N.: Approximating the independence number via the \u03b8-function. Math. Programming\u00a080, 253\u2013264 (1998)","journal-title":"Math. Programming"},{"key":"14_CR4","first-page":"9","volume-title":"Fete of Combinatorics, Bolyai Soc. Math. Studies 20","author":"N. Alon","year":"2010","unstructured":"Alon, N., Wormald, N.: High degree graphs contain large-star factors. In: Katona, G., Schrijver, A., Sz\u00f6nyi, T. (eds.) Fete of Combinatorics, Bolyai Soc. Math. Studies 20, pp. 9\u201321. Springer, Heidelberg (2010)"},{"key":"14_CR5","doi-asserted-by":"crossref","unstructured":"Austrin, P., Khot, S., Safra, M.: Inapproximability of Vertex Cover and Independent Set in Bounded Degree Graphs. In: IEEE Conference on Computational Complexity 2009, pp. 74\u201380 (2009)","DOI":"10.1109\/CCC.2009.38"},{"key":"14_CR6","first-page":"251","volume":"12","author":"P. Erd\u00f6s","year":"1963","unstructured":"Erd\u00f6s, P., Sachs, H.: Regul\u00e4re Graphen gegebener Taillenweite mit minimaler Knotenzahl (German). Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe\u00a012, 251\u2013257 (1963)","journal-title":"Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe"},{"key":"14_CR7","doi-asserted-by":"crossref","unstructured":"Goldreich, O., Ron, D.: Property testing in bounded degree graphs. In: Proc. 29th STOC, pp. 406\u2013415 (1997)","DOI":"10.1145\/258533.258627"},{"key":"14_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BFb0053959","volume-title":"Approximation Algorithms for Combinatorial Optimization","author":"M.M. Halld\u00f3rsson","year":"1998","unstructured":"Halld\u00f3rsson, M.M.: Approximations of Independent Sets in Graphs. In: Jansen, K., Rolim, J.D.P. (eds.) APPROX 1998. LNCS, vol.\u00a01444, pp. 1\u201313. Springer, Heidelberg (1998)"},{"key":"14_CR9","doi-asserted-by":"publisher","first-page":"1","DOI":"10.7155\/jgaa.00020","volume":"4","author":"M.M. Halld\u00f3rsson","year":"2000","unstructured":"Halld\u00f3rsson, M.M.: Approximations of Weighted Independent Set and Hereditary Subset Problems. Journal of Graphs Algorithms and Applications\u00a04, 1\u201316 (2000)","journal-title":"Journal of Graphs Algorithms and Applications"},{"key":"14_CR10","unstructured":"Halperin, E.: Improved approximation algorithms for the vertex cover problem in graphs and hypergraphs. In: Proc. Eleventh ACM-SIAM Symp. on Discrete Algorithms, pp. 329\u2013337 (2000)"},{"key":"14_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"475","DOI":"10.1007\/11830924_43","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"S. Marko","year":"2006","unstructured":"Marko, S., Ron, D.: Distance approximation in bounded-degree and general sparse graphs. In: D\u00edaz, J., Jansen, K., Rolim, J.D.P., Zwick, U. (eds.) APPROX 2006 and RANDOM 2006. LNCS, vol.\u00a04110, pp. 475\u2013486. Springer, Heidelberg (2006)"},{"key":"14_CR12","doi-asserted-by":"crossref","unstructured":"Nguyen, H.N., Onak, K.: Constant-Time Approximation Algorithms via Local Improvements. In: Proc. 49th Annual Symposium on Foundations of Computer Science (FOCS 2008), pp. 327\u2013336 (2008)","DOI":"10.1109\/FOCS.2008.81"},{"issue":"1-3","key":"14_CR13","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1016\/j.tcs.2007.04.040","volume":"381","author":"M. Parnas","year":"2007","unstructured":"Parnas, M., Ron, D.: Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms. Theoret. Comput. Sci.\u00a0381(1-3), 183\u2013196 (2007)","journal-title":"Theoret. Comput. Sci."},{"key":"14_CR14","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1002\/rsa.3240070305","volume":"7","author":"J.B. Shearer","year":"1995","unstructured":"Shearer, J.B.: On the independence number of sparse graphs. Random Structures and Algorithms\u00a07, 269\u2013271 (1995)","journal-title":"Random Structures and Algorithms"}],"container-title":["Lecture Notes in Computer Science","Property Testing"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-16367-8_14","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,21]],"date-time":"2019-03-21T14:44:42Z","timestamp":1553179482000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-16367-8_14"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642163661","9783642163678"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-16367-8_14","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}