{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,26]],"date-time":"2025-02-26T13:40:01Z","timestamp":1740577201090,"version":"3.38.0"},"publisher-location":"Berlin, Heidelberg","reference-count":23,"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_9","type":"book-chapter","created":{"date-parts":[[2010,10,7]],"date-time":"2010-10-07T15:25:55Z","timestamp":1286465155000},"page":"158-166","source":"Crossref","is-referenced-by-count":1,"title":["Sublinear Graph Approximation Algorithms"],"prefix":"10.1007","author":[{"given":"Krzysztof","family":"Onak","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"6","key":"9_CR1","doi-asserted-by":"publisher","first-page":"1370","DOI":"10.1137\/S0097539702403244","volume":"34","author":"B. Chazelle","year":"2005","unstructured":"Chazelle, B., Rubinfeld, R., Trevisan, L.: Approximating the minimum spanning tree weight in sublinear time. SIAM J. Comput.\u00a034(6), 1370\u20131379 (2005)","journal-title":"SIAM J. Comput."},{"issue":"1-3","key":"9_CR2","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. Theor. Comput. Sci.\u00a0381(1-3), 183\u2013196 (2007)","journal-title":"Theor. Comput. Sci."},{"key":"9_CR3","doi-asserted-by":"crossref","unstructured":"Kuhn, F., Moscibroda, T., Wattenhofer, R.: The price of being near-sighted. In: SODA, pp. 980\u2013989 (2006)","DOI":"10.1145\/1109557.1109666"},{"key":"9_CR4","doi-asserted-by":"crossref","unstructured":"Marko, S., Ron, D.: Approximating the distance to properties in bounded-degree and general sparse graphs. ACM Transactions on Algorithms\u00a05(2) (2009)","DOI":"10.1145\/1497290.1497298"},{"issue":"4","key":"9_CR5","doi-asserted-by":"publisher","first-page":"1036","DOI":"10.1137\/0215074","volume":"15","author":"M. Luby","year":"1986","unstructured":"Luby, M.: A simple parallel algorithm for the maximal independent set problem. SIAM J. Comput.\u00a015(4), 1036\u20131053 (1986)","journal-title":"SIAM J. Comput."},{"key":"9_CR6","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, New York (1979)"},{"key":"9_CR7","doi-asserted-by":"crossref","unstructured":"Nguyen, H.N., Onak, K.: Constant-time approximation algorithms via local improvements. In: FOCS, pp. 327\u2013336 (2008)","DOI":"10.1109\/FOCS.2008.81"},{"key":"9_CR8","doi-asserted-by":"crossref","unstructured":"Yoshida, Y., Yamamoto, M., Ito, H.: An improved constant-time approximation algorithm for maximum matchings. In: STOC, pp. 225\u2013234 (2009)","DOI":"10.1145\/1536414.1536447"},{"issue":"4","key":"9_CR9","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1137\/0202019","volume":"2","author":"J.E. Hopcroft","year":"1973","unstructured":"Hopcroft, J.E., Karp, R.M.: An n 5\/2 algorithm for maximum matchings in bipartite graphs. SIAM J. Comput.\u00a02(4), 225\u2013231 (1973)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"9_CR10","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1016\/S0022-0000(74)80044-9","volume":"9","author":"D.S. Johnson","year":"1974","unstructured":"Johnson, D.S.: Approximation algorithms for combinatorial problems. J. Comput. Syst. Sci.\u00a09(3), 256\u2013278 (1974)","journal-title":"J. Comput. Syst. Sci."},{"key":"9_CR11","doi-asserted-by":"publisher","first-page":"383","DOI":"10.1016\/0012-365X(75)90058-8","volume":"13","author":"L. Lov\u00e1sz","year":"1975","unstructured":"Lov\u00e1sz, L.: On the ratio of optimal integral and fractional covers. Discrete Mathematics\u00a013, 383\u2013390 (1975)","journal-title":"Discrete Mathematics"},{"key":"9_CR12","unstructured":"Alon, N.: On constant time approximation of parameters of bounded degree graphs"},{"issue":"10","key":"9_CR13","doi-asserted-by":"publisher","first-page":"2667","DOI":"10.1016\/j.jfa.2008.01.010","volume":"254","author":"G. Elek","year":"2008","unstructured":"Elek, G.: L 2-spectral invariants and convergent sequences of finite graphs. Journal of Functional Analysis\u00a0254(10), 2667\u20132689 (2008)","journal-title":"Journal of Functional Analysis"},{"key":"9_CR14","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1137\/0136016","volume":"36","author":"R.J. Lipton","year":"1979","unstructured":"Lipton, R.J., Tarjan, R.E.: A separator theorem for planar graphs. SIAM Journal on Applied Mathematics\u00a036, 177\u2013189 (1979)","journal-title":"SIAM Journal on Applied Mathematics"},{"key":"9_CR15","doi-asserted-by":"crossref","unstructured":"Alon, N., Seymour, P.D., Thomas, R.: A separator theorem for graphs with an excluded minor and its applications. In: STOC, pp. 293\u2013299 (1990)","DOI":"10.1145\/100216.100254"},{"issue":"6","key":"9_CR16","doi-asserted-by":"publisher","first-page":"2499","DOI":"10.1137\/070681831","volume":"38","author":"A. Czumaj","year":"2009","unstructured":"Czumaj, A., Shapira, A., Sohler, C.: Testing hereditary properties of nonexpanding bounded-degree graphs. SIAM J. Comput.\u00a038(6), 2499\u20132510 (2009)","journal-title":"SIAM J. Comput."},{"key":"9_CR17","doi-asserted-by":"crossref","unstructured":"Hassidim, A., Kelner, J.A., Nguyen, H.N., Onak, K.: Local graph partitions for approximation and testing. In: FOCS (2009)","DOI":"10.1109\/FOCS.2009.77"},{"key":"9_CR18","doi-asserted-by":"crossref","unstructured":"Elek, G.: Parameter testing with bounded degree graphs of subexponential growth. arXiv:0711.2800v3 (2009)","DOI":"10.1002\/rsa.20308"},{"issue":"2","key":"9_CR19","doi-asserted-by":"publisher","first-page":"302","DOI":"10.1007\/s00453-001-0078-7","volume":"32","author":"O. Goldreich","year":"2002","unstructured":"Goldreich, O., Ron, D.: Property testing in bounded degree graphs. Algorithmica\u00a032(2), 302\u2013343 (2002)","journal-title":"Algorithmica"},{"key":"9_CR20","doi-asserted-by":"crossref","unstructured":"Benjamini, I., Schramm, O., Shapira, A.: Every minor-closed property of sparse graphs is testable. In: STOC, pp. 393\u2013402 (2008)","DOI":"10.1145\/1374376.1374433"},{"issue":"2","key":"9_CR21","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1016\/j.jctb.2004.08.001","volume":"92","author":"N. Robertson","year":"2004","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. XX. Wagner\u2019s conjecture. Journal of Combinatorial Theory, Series B\u00a092(2), 325\u2013357 (2004); Special Issue Dedicated to Professor W.T. Tutte","journal-title":"Journal of Combinatorial Theory, Series B"},{"issue":"6","key":"9_CR22","doi-asserted-by":"publisher","first-page":"1703","DOI":"10.1137\/06064888X","volume":"37","author":"N. Alon","year":"2008","unstructured":"Alon, N., Shapira, A.: A characterization of the (natural) graph properties testable with one-sided error. SIAM J. Comput.\u00a037(6), 1703\u20131727 (2008)","journal-title":"SIAM J. Comput."},{"key":"9_CR23","doi-asserted-by":"crossref","unstructured":"Bogdanov, A., Obata, K., Trevisan, L.: A lower bound for testing 3-colorability in bounded-degree graphs. In: FOCS, pp. 93\u2013102 (2002)","DOI":"10.1109\/SFCS.2002.1181886"}],"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_9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,26]],"date-time":"2025-02-26T13:17:55Z","timestamp":1740575875000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-16367-8_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642163661","9783642163678"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-16367-8_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}