{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T06:10:35Z","timestamp":1725516635388},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540850960"},{"type":"electronic","value":"9783540850977"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-85097-7_8","type":"book-chapter","created":{"date-parts":[[2008,8,19]],"date-time":"2008-08-19T07:18:26Z","timestamp":1219130306000},"page":"79-88","source":"Crossref","is-referenced-by-count":0,"title":["Separating Sublinear Time Computations by Approximate Diameter"],"prefix":"10.1007","author":[{"given":"Bin","family":"Fu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zhiyu","family":"Zhao","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"8_CR1","doi-asserted-by":"crossref","unstructured":"Badoiu, M., Czumaj, A., Indyk, P., Sohler, C.: Facility location in sublinear time. In: Proceedings of 32nd Annual International Colloquium on Automata, Languages and Programming, pp. 866\u2013877 (2005)","DOI":"10.1007\/11523468_70"},{"key":"8_CR2","doi-asserted-by":"publisher","first-page":"627","DOI":"10.1137\/S009753970444572X","volume":"35","author":"B. Chazelle","year":"2005","unstructured":"Chazelle, B., Liu, D., Magen, A.: Sublinear geometric algorithms. SIAM Journal on Computing\u00a035, 627\u2013646 (2005)","journal-title":"SIAM Journal on Computing"},{"key":"8_CR3","doi-asserted-by":"publisher","first-page":"1370","DOI":"10.1137\/S0097539702403244","volume":"34","author":"B. Chazelle","year":"2005","unstructured":"Chazelle, B., Rubfinfeld, R., Trevisan, L.: Approximating the minimum spanning tree weight in sublinear time. SIAM Journal on computing\u00a034, 1370\u20131379 (2005)","journal-title":"SIAM Journal on computing"},{"key":"8_CR4","unstructured":"Chen, L., Fu, B.: Linear and sublinear time algorithms for the basis of abelian groups. Electronic Colloquium on Computational Complexity, TR07-052 (2007)"},{"key":"8_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, I.N.A., Rubinfeld, R., Sohler, C.: Sublinear approximation of euclidean minimum spanning tree. SIAM Journal on Computing\u00a035, 91\u2013109 (2005)","journal-title":"SIAM Journal on Computing"},{"key":"8_CR6","doi-asserted-by":"crossref","unstructured":"Czumaj, A., Sohler, C.: Estimating the weight of metric minimum spanning trees in sublinear-time. In: Proceedings of the 36th Annual ACM Symposium on Theory of Computing, pp. 175\u2013183 (2004)","DOI":"10.1145\/1007352.1007386"},{"key":"8_CR7","doi-asserted-by":"crossref","unstructured":"Drineas, P., Kannan, R.: Fast monte-carlo algorithms for approximate matrix multiplication. In: Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science, pp. 452\u2013459 (2001)","DOI":"10.1109\/SFCS.2001.959921"},{"key":"8_CR8","doi-asserted-by":"publisher","first-page":"964","DOI":"10.1137\/S0097539704447304","volume":"35","author":"U. Feige","year":"2006","unstructured":"Feige, U.: On sumes of independent random variables with unbounded variance and estimating the average degree in a graph. SIAM Journal on Computing\u00a035, 964\u2013984 (2006)","journal-title":"SIAM Journal on Computing"},{"key":"8_CR9","first-page":"97","volume":"75","author":"E. Fischer","year":"2001","unstructured":"Fischer, E.: The art of uninformed decision: A primer to property testing. Bulletin of the EATCS\u00a075, 97\u2013126 (2001)","journal-title":"Bulletin of the EATCS"},{"key":"8_CR10","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1007\/s10878-007-9092-2","volume":"15","author":"B. Fu","year":"2008","unstructured":"Fu, B., Chen, Z.: Sublinear-time algorithms for width-bounded geometric separators and their applications to protein side-chain packing problems. Journal of Combinatorial Optimization\u00a015, 387\u2013407 (2008)","journal-title":"Journal of Combinatorial Optimization"},{"key":"8_CR11","doi-asserted-by":"crossref","unstructured":"Goldreich, O.: Combinatorial proterty testing (a survey). In: Pardalos, P., Rajasekaran, S., Rolim, J. (eds.) Proceedings of the DIMACS workshop on radnomziation methods in algorithm design, vol.\u00a043, pp. 45\u201359 (1997)","DOI":"10.1090\/dimacs\/043\/04"},{"key":"8_CR12","doi-asserted-by":"crossref","unstructured":"Goldreich, O.: Property testing in massive graphs. In: Abello, J., Pardalos, P.M., Resende, M. (eds.) Handbook of massive data sets, pp. 123\u2013147 (2002)","DOI":"10.1007\/978-1-4615-0005-6_5"},{"key":"8_CR13","unstructured":"Goldreich, O., Ron, D.: On testing expansion in bounded-degree graphs. Technical Report 00-20, Electronic Colloquium on Computational Complexity, http:\/\/www.eccc.uni-trier.de\/eccc\/ (2000)"},{"key":"8_CR14","unstructured":"Goldreich, O., Ron, D.: Approximating average parameters of graphs. Technical Report 05-73, Electronic Colloquium on Computational Complexity (2005), http:\/\/www.eccc.uni-trier.de\/eccc\/"},{"key":"8_CR15","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1145\/954092.954103","volume":"34","author":"R. Kumar","year":"2003","unstructured":"Kumar, R., Rubinfeld, R.: Sublinear time algorithms. SIGACT News\u00a034, 57\u201367 (2003)","journal-title":"SIGACT News"},{"key":"8_CR16","doi-asserted-by":"publisher","first-page":"653","DOI":"10.1145\/285055.285060","volume":"45","author":"S.G.O. Goldreich","year":"1998","unstructured":"Goldreich, S.G.O., Ron, D.: Property testing and its connection to learning and approximation. J. ACM\u00a045, 653\u2013750 (1998)","journal-title":"J. ACM"},{"key":"8_CR17","doi-asserted-by":"crossref","unstructured":"Ron, D.: Handbook of randomzied algorithm. Bulletin of the EATCS II, 597\u2013649 (2001)","DOI":"10.1007\/978-1-4615-0013-1_15"},{"key":"8_CR18","doi-asserted-by":"crossref","unstructured":"Zhao, Z., Fu, B.: A flexible algorithm for pairwise protein structure alignment. In: Proceedings International Conference on Bioinformatics and Computational Biology 2007 (2007)","DOI":"10.1142\/9781848162648_0010"},{"key":"8_CR19","doi-asserted-by":"crossref","unstructured":"Zimand, M.: On derandomizing probabilistic sublinear-time algorithms. In: Proceedings of the 22nd IEEE conference on computational complexity, pp. 1\u20139 (2007)","DOI":"10.1109\/CCC.2007.19"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Optimization and Applications"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-85097-7_8.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,24]],"date-time":"2020-11-24T02:21:57Z","timestamp":1606184517000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-85097-7_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540850960","9783540850977"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-85097-7_8","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[]}}