{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T23:45:49Z","timestamp":1725493549044},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540422877"},{"type":"electronic","value":"9783540482246"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-48224-5_16","type":"book-chapter","created":{"date-parts":[[2007,10,28]],"date-time":"2007-10-28T02:29:04Z","timestamp":1193538544000},"page":"190-200","source":"Crossref","is-referenced-by-count":11,"title":["Approximating the Minimum Spanning Tree Weight in Sublinear Time"],"prefix":"10.1007","author":[{"given":"Bernard","family":"Chazelle","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ronitt","family":"Rubinfeld","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Luca","family":"Trevisan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2001,7,4]]},"reference":[{"key":"16_CR1","doi-asserted-by":"crossref","unstructured":"Alon, N., Dar, S., Parnas, M., Ron, D., Testing of clustering, Proc. FOCS, 2000.","DOI":"10.1109\/SFCS.2000.892111"},{"key":"16_CR2","doi-asserted-by":"publisher","first-page":"1028","DOI":"10.1145\/355541.355562","volume":"47","author":"B. Chazelle","year":"2000","unstructured":"Chazelle, B., A minimum spanning tree algorithm with inverse-Ackermann type complexity, J. ACM, 47 (2000), 1028\u20131047.","journal-title":"J. ACM"},{"key":"16_CR3","doi-asserted-by":"crossref","unstructured":"Chazelle, B., The Discrepancy Method: Randomness and Complexity, Cambridge University Press, 2000.","DOI":"10.1017\/CBO9780511626371"},{"key":"16_CR4","unstructured":"Eppstein, D., Representing all minimum spanning trees with applications to counting and generation, Tech. Rep. 95-50, ICS, UCI, 1995."},{"key":"16_CR5","doi-asserted-by":"publisher","first-page":"424","DOI":"10.1016\/0022-0000(93)90040-4","volume":"48","author":"M.L. Fredman","year":"1993","unstructured":"Fredman, M.L., Willard, D.E. Trans-dichotomous algorithms for minimum spanning trees and shortest paths, J. Comput. and System Sci., 48 (1993), 424\u2013436.","journal-title":"J. Comput. and System Sci."},{"key":"16_CR6","doi-asserted-by":"crossref","unstructured":"Frieze, A., Kannan, R. Quick approximation to matrices and applications, Combinatorica, 19 (1999)","DOI":"10.1007\/s004930050052"},{"key":"16_CR7","doi-asserted-by":"crossref","unstructured":"Frieze, A., Kannan, R., Vempala, S., Fast monte-carlo algorithms for finding low-rank approximations, Proc. 39th FOCS (1998).","DOI":"10.1109\/SFCS.1998.743487"},{"key":"16_CR8","doi-asserted-by":"crossref","unstructured":"Goldreich, O., Goldwasser, S., Ron, D., Property testing and its connection to learning and approximation, Proc. 37th FOCS (1996), 339\u2013348.","DOI":"10.1109\/SFCS.1996.548493"},{"key":"16_CR9","doi-asserted-by":"crossref","unstructured":"Goldreich, O., Ron, D., Property testing in bounded degree graphs, Proc. 29th STOC (1997), 406\u2013415.","DOI":"10.1145\/258533.258627"},{"key":"16_CR10","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1109\/MAHC.1985.10011","volume":"7","author":"R.L. Graham","year":"1985","unstructured":"Graham, R.L., Hell, P. On the history of the minimum spanning tree problem, Ann. Hist. Comput. 7 (1985), 43\u201357.","journal-title":"Ann. Hist. Comput."},{"key":"16_CR11","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1145\/201019.201022","volume":"42","author":"D.R. Karger","year":"1995","unstructured":"Karger, D.R., Klein, P.N, Tarjan, R.E., A randomized linear-time algorithm to find minimum spanning trees, J. ACM, 42 (1995), 321\u2013328.","journal-title":"J. ACM"},{"key":"16_CR12","first-page":"15","volume":"33","author":"J. Ne\u0161et\u0159il","year":"1997","unstructured":"Ne\u0161et\u0159il, J. A few remarks on the history of MST-problem, Archivum Mathematicum, Brno 33 (1997), 15\u201322. Prelim. version in KAM Series, Charles University, Prague, No. 97-338, 1997.","journal-title":"Archivum Mathematicum, Brno"},{"key":"16_CR13","doi-asserted-by":"crossref","unstructured":"Pettie, S., Ramachandran, V. An optimal minimum spanning tree algorithm, Proc. 27th ICALP (2000).","DOI":"10.1007\/3-540-45022-X_6"},{"key":"16_CR14","unstructured":"Ron, D., Property testing (a tutorial), to appear in \u201cHandbook on Randomization.\u201d"},{"key":"16_CR15","doi-asserted-by":"publisher","first-page":"252","DOI":"10.1137\/S0097539793255151","volume":"25","author":"R. Rubinfeld","year":"1996","unstructured":"Rubinfeld, R., Sudan, M., Robust characterizations of polynomials with applications to program testing, SIAM J. Comput. 25 (1996), 252\u2013271.","journal-title":"SIAM J. Comput."}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-48224-5_16","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,2,24]],"date-time":"2019-02-24T14:09:27Z","timestamp":1551017367000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-48224-5_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540422877","9783540482246"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/3-540-48224-5_16","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2001]]}}}