{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T13:13:49Z","timestamp":1743081229255,"version":"3.40.3"},"publisher-location":"Cham","reference-count":27,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319919072"},{"type":"electronic","value":"9783319919089"}],"license":[{"start":{"date-parts":[[2019,1,1]],"date-time":"2019-01-01T00:00:00Z","timestamp":1546300800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2019]]},"DOI":"10.1007\/978-3-319-91908-9_7","type":"book-chapter","created":{"date-parts":[[2019,10,4]],"date-time":"2019-10-04T09:05:00Z","timestamp":1570179900000},"page":"105-122","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Sublinear-Time Algorithms for Approximating Graph Parameters"],"prefix":"10.1007","author":[{"given":"Dana","family":"Ron","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,10,5]]},"reference":[{"key":"7_CR1","unstructured":"Aliakbarpour, M., Biswas, A.S., Gouleakis, T., Peebles, J., Rubinfeld, R., Yodpinyanee, A.: Sublinear-time algorithms for counting star subgraphs with applications to join selectivity estimation. Technical report 1601.04233, Arxiv (2016). To appear in Algorithmica. 107"},{"key":"7_CR2","unstructured":"Bansal, V.: Sublinear-time algorithms for estimating the weight of minimum spanning trees. Unpublished manuscript (2003). 109"},{"key":"7_CR3","unstructured":"Bogdanov, A., Obata, K., Trevisan, L.: A lower bound for testing 3-colorability in bounded-degree graphs. In: Proceedings of FOCS, Los Alamitos, CA, pp. 93\u2013102 (2002). 108"},{"issue":"6","key":"7_CR4","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. 34(6), 1370\u20131379 (2005). 108, 109, 120","journal-title":"SIAM J. Comput."},{"issue":"1","key":"7_CR5","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1137\/S0097539703435297","volume":"35","author":"A Czumaj","year":"2005","unstructured":"Czumaj, A., Ergun, F., Fortnow, L., Magen, A., Newman, I., Rubinfeld, R., Sohler, C.: Approximating the weight of the euclidean minimum spanning tree in sublinear time. SIAM J. Comput. 35(1), 91\u2013109 (2005). 109","journal-title":"SIAM J. Comput."},{"issue":"3","key":"7_CR6","doi-asserted-by":"publisher","first-page":"904","DOI":"10.1137\/060672121","volume":"39","author":"A Czumaj","year":"2009","unstructured":"Czumaj, A., Sohler, C.: Estimating the weight of metric minimum spanning trees in sublinear time. SIAM J. Comput. 39(3), 904\u2013922 (2009). 109, 120","journal-title":"SIAM J. Comput."},{"issue":"5","key":"7_CR7","doi-asserted-by":"publisher","first-page":"1603","DOI":"10.1137\/15M1054389","volume":"46","author":"T Eden","year":"2017","unstructured":"Eden, T., Levi, A., Ron, D., Seshadhri, C.: Approximately counting triangles in sublinear time. SIAM J. Comput. 46(5), 1603\u20131646 (2017). 107","journal-title":"SIAM J. Comput."},{"key":"7_CR8","doi-asserted-by":"crossref","unstructured":"Eden, T., Ron, D., Seshadhri, C.: On approximating the number of $$k$$ -cliques in sublinear time. CoRR, abs\/1707.04858 (2017). 107","DOI":"10.1145\/3188745.3188810"},{"key":"7_CR9","unstructured":"Eden, T., Ron, D., Seshadhri, C.: Sublinear time estimation of degree distribution moments: the arboricity connection. In: Proceedings of ICALP, pp. 7:1\u20137:13 (2017). 106, 107, 110, 114"},{"issue":"4","key":"7_CR10","doi-asserted-by":"publisher","first-page":"964","DOI":"10.1137\/S0097539704447304","volume":"35","author":"U Feige","year":"2006","unstructured":"Feige, U.: On sums of independent random variables with unbounded variance, and estimating the average degree in a graph. SIAM J. Comput. 35(4), 964\u2013984 (2006). 106","journal-title":"SIAM J. Comput."},{"issue":"2","key":"7_CR11","doi-asserted-by":"publisher","first-page":"482","DOI":"10.1137\/060652324","volume":"37","author":"E Fischer","year":"2007","unstructured":"Fischer, E., Newman, I.: Testing versus estimation of graph properties. SIAM J. Comput. 37(2), 482\u2013501 (2007). 110","journal-title":"SIAM J. Comput."},{"key":"7_CR12","doi-asserted-by":"publisher","first-page":"653","DOI":"10.1145\/285055.285060","volume":"45","author":"O Goldreich","year":"1998","unstructured":"Goldreich, O., Goldwasser, S., Ron, D.: Property testing and its connections to learning and approximation. J. ACM 45, 653\u2013750 (1998). 110","journal-title":"J. ACM"},{"key":"7_CR13","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 32, 302\u2013343 (2002). 110","journal-title":"Algorithmica"},{"issue":"4","key":"7_CR14","doi-asserted-by":"publisher","first-page":"473","DOI":"10.1002\/rsa.20203","volume":"32","author":"O Goldreich","year":"2008","unstructured":"Goldreich, O., Ron, D.: Approximating average parameters of graphs. Random Struct. Algorithms 32(4), 473\u2013493 (2008). 106, 111","journal-title":"Random Struct. Algorithms"},{"issue":"3","key":"7_CR15","doi-asserted-by":"publisher","first-page":"1365","DOI":"10.1137\/100783066","volume":"25","author":"M Gonen","year":"2011","unstructured":"Gonen, M., Ron, D., Shavitt, Y.: Counting stars and other small subgraphs in sublinear time. SIAM J. Discret. Math. 25(3), 1365\u20131411 (2011). 106, 107","journal-title":"SIAM J. Discret. Math."},{"key":"7_CR16","doi-asserted-by":"crossref","unstructured":"Hassidim, A., Kelner, J.A., Nguyen, H.N., Onak, K.: Local graph partitions for approximation and testing. In: Proceedings of FOCS, pp. 22\u201331 (2009). 108","DOI":"10.1109\/FOCS.2009.77"},{"issue":"3","key":"7_CR17","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1145\/2629508","volume":"11","author":"R Levi","year":"2015","unstructured":"Levi, R., Ron, D.: A quasi-polynomial time partition oracle for graphs with an excluded minor. ACM Trans. Algorithms 11(3), 24 (2015). 109","journal-title":"ACM Trans. Algorithms"},{"issue":"2","key":"7_CR18","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. 15(2), 1036\u20131055 (1986). 115","journal-title":"SIAM J. Comput."},{"issue":"2","key":"7_CR19","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1145\/1497290.1497298","volume":"5","author":"S Marko","year":"2009","unstructured":"Marko, S., Ron, D.: Distance approximation in bounded-degree and general sparse graphs. ACM Trans. Algorithms 5(2), 22 (2009). 108, 110, 115","journal-title":"ACM Trans. Algorithms"},{"issue":"1","key":"7_CR20","doi-asserted-by":"publisher","first-page":"445","DOI":"10.1112\/jlms\/s1-36.1.445","volume":"1","author":"CSJA Nash-Williams","year":"1961","unstructured":"Nash-Williams, C.S.J.A.: Edge-disjoint spanning trees of finite graphs. J. Lond. Math. Soc. 1(1), 445\u2013450 (1961). 107","journal-title":"J. Lond. Math. Soc."},{"issue":"1","key":"7_CR21","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1112\/jlms\/s1-39.1.12","volume":"1","author":"CSJA Nash-Williams","year":"1964","unstructured":"Nash-Williams, C.S.J.A.: Decomposition of finite graphs into forests. J. Lond. Math. Soc. 1(1), 12 (1964). 107","journal-title":"J. Lond. Math. Soc."},{"key":"7_CR22","unstructured":"Nguyen, H.N., Onak, K.: Constant-time approximation algorithms via local improvements. In: Proceedings of FOCS, pp. 327\u2013336 (2008). 108, 109, 118, 119"},{"key":"7_CR23","doi-asserted-by":"crossref","unstructured":"Onak, K., Ron, D., Rosen, M., Rubinfeld, R.: A near-optimal sublinear-time algorithm for approximating the minimum vertex cover size. In: Proceedings of SODA, pp. 1123\u20131131 (2012). 108, 119","DOI":"10.1137\/1.9781611973099.88"},{"issue":"1\u20133","key":"7_CR24","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. 381(1\u20133), 183\u2013196 (2007). 108, 115, 117, 120","journal-title":"Theoret. Comput. Sci."},{"issue":"6","key":"7_CR25","doi-asserted-by":"publisher","first-page":"1012","DOI":"10.1016\/j.jcss.2006.03.002","volume":"72","author":"M Parnas","year":"2006","unstructured":"Parnas, M., Ron, D., Rubinfeld, R.: Tolerant property testing and distance approximation. J. Comput. Syst. Sci. 72(6), 1012\u20131042 (2006). 109, 110","journal-title":"J. Comput. Syst. Sci."},{"key":"7_CR26","unstructured":"Seshadhri. C.: A simpler sublinear algorithm for approximating the triangle count. CoRR, abs\/1505.01927 (2015). 111"},{"issue":"4","key":"7_CR27","doi-asserted-by":"publisher","first-page":"1074","DOI":"10.1137\/110828691","volume":"41","author":"Y Yoshida","year":"2012","unstructured":"Yoshida, Y., Yamamoto, M., Ito, H.: An improved constant-time approximation algorithm for maximum matchings and other optimization problems. SIAM J. Comput. 41(4), 1074\u20131093 (2012). 108, 109, 119","journal-title":"SIAM J. Comput."}],"container-title":["Lecture Notes in Computer Science","Computing and Software Science"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-91908-9_7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,1]],"date-time":"2022-10-01T00:18:28Z","timestamp":1664583508000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-91908-9_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019]]},"ISBN":["9783319919072","9783319919089"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-91908-9_7","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2019]]},"assertion":[{"value":"5 October 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}