{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,6]],"date-time":"2022-04-06T00:20:19Z","timestamp":1649204419087},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2009,8,19]],"date-time":"2009-08-19T00:00:00Z","timestamp":1250640000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2009,11]]},"DOI":"10.1007\/s10878-009-9248-3","type":"journal-article","created":{"date-parts":[[2009,8,18]],"date-time":"2009-08-18T16:27:15Z","timestamp":1250612835000},"page":"393-416","source":"Crossref","is-referenced-by-count":0,"title":["Separating sublinear time computations by\u00a0approximate diameter"],"prefix":"10.1007","volume":"18","author":[{"given":"Bin","family":"Fu","sequence":"first","affiliation":[]},{"given":"Zhiyu","family":"Zhao","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2009,8,19]]},"reference":[{"key":"9248_CR1","doi-asserted-by":"crossref","unstructured":"Badoiu M, Czumaj A, Indyk P, Sohler C (2005) Facility location in sublinear time. In: Proceedings of 32nd annual international colloquium on automata, languages and programming, pp 866\u2013877","DOI":"10.1007\/11523468_70"},{"key":"9248_CR2","doi-asserted-by":"crossref","first-page":"627","DOI":"10.1137\/S009753970444572X","volume":"35","author":"B Chazelle","year":"2005","unstructured":"Chazelle B, Liu D, Magen A (2005a) Sublinear geometric algorithms. SIAM J Comput 35:627\u2013646","journal-title":"SIAM J Comput"},{"key":"9248_CR3","doi-asserted-by":"crossref","first-page":"1370","DOI":"10.1137\/S0097539702403244","volume":"34","author":"B Chazelle","year":"2005","unstructured":"Chazelle B, Rubfinfeld R, Trevisan L (2005b) Approximating the minimum spanning tree weight in sublinear time. SIAM J Comput 34:1370\u20131379","journal-title":"SIAM J Comput"},{"key":"9248_CR4","unstructured":"Chen L, Fu B (2007) Linear and sublinear time algorithms for the basis of Abelian groups. Electron Colloq Comput Complex TR07-052"},{"key":"9248_CR5","doi-asserted-by":"crossref","unstructured":"Czumaj A, Sohler C (2004) 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","DOI":"10.1145\/1007352.1007386"},{"key":"9248_CR6","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1137\/S0097539703435297","volume":"35","author":"A Czumaj","year":"2005","unstructured":"Czumaj A, Ergun F, Fortnow L, Magen INA, Rubinfeld R, Sohler C (2005) Sublinear approximation of euclidean minimum spanning tree. SIAM J Comput 35:91\u2013109","journal-title":"SIAM J Comput"},{"key":"9248_CR7","doi-asserted-by":"crossref","unstructured":"Drineas P, Kannan R (2001) Fast Monte-Carlo algorithms for approximate matrix multiplication. In: Proceedings of the 42nd IEEE Symposium on Foundations of Computer. Science, pp 452\u2013459","DOI":"10.1109\/SFCS.2001.959921"},{"key":"9248_CR8","doi-asserted-by":"crossref","first-page":"964","DOI":"10.1137\/S0097539704447304","volume":"35","author":"U Feige","year":"2006","unstructured":"Feige U (2006) On sums of independent random variables with unbounded variance and estimating the average degree in a graph. SIAM J Comput 35:964\u2013984","journal-title":"SIAM J Comput"},{"key":"9248_CR9","first-page":"97","volume":"75","author":"E Fischer","year":"2001","unstructured":"Fischer E (2001) The art of uninformed decision: a primer to property testing. Bull EATCS 75:97\u2013126","journal-title":"Bull EATCS"},{"issue":"4","key":"9248_CR10","doi-asserted-by":"crossref","first-page":"387","DOI":"10.1007\/s10878-007-9092-2","volume":"15","author":"B Fu","year":"2008","unstructured":"Fu B, Chen Z (2008) Sublinear time width-bounded separators and their applications to the protein side-chain packing problem. J Comb Optim 15(4):387\u2013407","journal-title":"J Comb Optim"},{"key":"9248_CR11","doi-asserted-by":"crossref","unstructured":"Goldreich O (1997) Combinatorial property testing (a survey). In: Pardalos P, Rajasekaran S, Rolim J (eds) Proceesdings of the DIMACS workshop on radnomziation methods in algorithm design. DIMACS series in discrete mathematics and theoretical computer science, vol 43, pp 45\u201359","DOI":"10.1090\/dimacs\/043\/04"},{"key":"9248_CR12","doi-asserted-by":"crossref","unstructured":"Goldreich O (2002) Property testing in massive graphs. In: Abello J, Pardalos PM, Resende M (eds) Handbook of massive data sets, pp 123\u2013147","DOI":"10.1007\/978-1-4615-0005-6_5"},{"key":"9248_CR13","unstructured":"Goldreich O, Ron D (2000) On testing expansion in bounded-degree graphs. Technical Report 00-20, Electronic Colloquium on Computational Complexity. http:\/\/www.eccc.uni-trier.de\/eccc\/"},{"key":"9248_CR14","unstructured":"Goldreich O, Ron D (2005) Approximating average parameters of graphs. Technical Report 05-73, Electronic Colloquium on Computational Complexity. http:\/\/www.eccc.uni-trier.de\/eccc\/"},{"key":"9248_CR15","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1145\/954092.954103","volume":"34","author":"R Kumar","year":"2003","unstructured":"Kumar R, Rubinfeld R (2003) Sublinear time algorithms. SIGACT News 34:57\u201367","journal-title":"SIGACT News"},{"key":"9248_CR16","doi-asserted-by":"crossref","first-page":"653","DOI":"10.1145\/285055.285060","volume":"45","author":"SGO Goldreich","year":"1998","unstructured":"Goldreich SGO, Ron D (1998) Property testing and its connection to learning and approximation. J ACM 45:653\u2013750","journal-title":"J ACM"},{"key":"9248_CR17","first-page":"597","volume":"II","author":"D Ron","year":"2001","unstructured":"Ron D (2001) Handbook of randomized algorithm. Bull EATCS II:597\u2013649","journal-title":"Bull EATCS"},{"key":"9248_CR18","volume-title":"Advanced calculus","author":"WF Trench","year":"1978","unstructured":"Trench WF (1978) Advanced calculus. Harper & Row, New York"},{"key":"9248_CR19","doi-asserted-by":"crossref","unstructured":"Zhao Z, Fu B (2007) A flexible algorithm for pairwise protein structure alignment. In: Proceedings international conference on bioinformatics and computational biology","DOI":"10.1142\/9781848162648_0010"},{"key":"9248_CR20","doi-asserted-by":"crossref","unstructured":"Zimand M (2007) On derandomizing probabilistic sublinear-time algorithms. In: Proceedings of the 22nd IEEE conference on computational complexity, pp 1\u20139","DOI":"10.1109\/CCC.2007.19"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-009-9248-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-009-9248-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-009-9248-3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,31]],"date-time":"2019-05-31T00:18:14Z","timestamp":1559261894000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-009-9248-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,8,19]]},"references-count":20,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2009,11]]}},"alternative-id":["9248"],"URL":"https:\/\/doi.org\/10.1007\/s10878-009-9248-3","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,8,19]]}}}