[1] N. Alon, S. Dar, M. Parnas, and D. Ron, Testing of clustering, SIAM J. Discrete Math.,
16 (2003), pp. 393–417.
[2] T. Batu, F. Erg¨un, J. Kilian, A. Magen, S. Raskhodnikova, R. Rubinfeld, and R. Sami,
A sublinear algorithm for weakly approximating edit distance, in Proceedings of the 35th
Annual ACM Symposium on Theory of Computing (STOC), 2003, pp. 316–324.
[3] P. Berenbrink, F. Erg¨un, and T. Friedetzky, Finding frequent patterns in a string in
sublinear time, in Proceedings of the 13th Annual European Symposium on Algorithms
(ESA), Springer-Verlag, Berlin, 2005, pp. 746–757.
[4] P. B. Callahan and S. R. Kosaraju, A decomposition of multidimensional point sets with
applications to k-nearest-neighbors and n-body potential fields, J. ACM, 42 (1995), pp.
67–90.
[5] B. Chazelle, A minimum spanning tree algorithm with inverse-Ackermann type complexity,
J. ACM, 47 (2000), pp. 1012–1027.
[6] B. Chazelle, D. Liu, and A. Magen, Sublinear geometric algorithms, SIAM J. Comput., 35
(2006), pp. 627–646.
[7] B. Chazelle, R. Rubinfeld, and L. Trevisan, Approximating the minimum spanning tree
weight in sublinear time, SIAM J. Comput., 34 (2005), pp. 1370–1379.
[8] A. Czumaj, F. Erg¨un, L. Fortnow, A. Magen, I. Newman, R. Rubinfeld, and C. Sohler,
Approximating the weight of the Euclidean minimum spanning tree in sublinear time,
SIAM J. Comput., 35 (2005), pp. 91–109.
[9] A. Czumaj and C. Sohler, Sublinear-time algorithms, Bull. Eur. Assoc. Theor. Comput. Sci.
EATCS, 89 (2006), pp. 23–47.
[10] D. Eppstein, Spanning trees and spanners, in Handbook of Computational Geometry, J.-R.
Sack and J. Urrutia, eds., North–Holland, Amsterdam, 2000, pp. 425–461.
[11] F. Erg¨un, S. Muthukrishnan, and C. Sahinalp, Sublinear methods for detecting periodic
trends in data streams, in Proceedings of the 6th Latin American Symposium on Theoretical
Informatics (LATIN), Springer-Verlag, Berlin, 2004, pp. 16–28.
[12] A. Frieze and R. Kannan, The regularity lemma and approximation schemes for dense problems,
in Proceedings of the 37th IEEE Symposium on Foundations of Computer Science
(FOCS), 1996, pp. 12–20.
[13] A. Frieze, R. Kannan, and S. Vempala, Fast Monte-Carlo algorithms for finding low-rank
approximations, J. ACM, 51 (2004), pp. 1025–1041.
[14] O. Goldreich, S. Goldwasser, and D. Ron, Property testing and its connection to learning
and approximation, J. ACM, 45 (1998), pp. 653–750.
[15] O. Goldreich and D. Ron, Approximating average parameters of graphs, in Proceedings of the
10th International Workshop on Randomization and Computation (RANDOM), Springer-
Verlag, Berlin, Heidelberg, 2006, pp. 363–374.
[16] A. Hajnal and E. Szemer´edi, Proof of a conjecture of P. Erd˝os, in Combinatorial Theory and
Its Applications, Vol. 2, P. Erd˝os, A. R´enyi, and V. T. S´os, eds., North–Holland, London,
1970, pp. 601–623.
[17] P. Indyk, A sublinear time approximation scheme for clustering in metric spaces, in Proceedings
of the 39th IEEE Symposium on Foundations of Computer Science (FOCS), 1998, pp.
154–159.
[18] P. Indyk, Sublinear time algorithms for metric space problems, in Proceedings of the 31st
Annual ACM Symposium on Theory of Computing (STOC), 1999, pp. 428–434.
[19] D. R. Karger, P. N. Klein, and R. E. Tarjan, A randomized linear-time algorithm to find
minimum spanning trees, J. ACM, 42 (1995), pp. 321–328.
[20] N. Mishra, D. Oblinger, and L. Pitt, Sublinear time approximate clustering, in Proceedings
of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2001, pp.
439–447.
[21] M. Parnas and D. Ron, Approximating the minimum vertex cover in sublinear time and a
connection to distributed algorithms, Theoret. Comput. Sci., 381 (2007), pp. 183–196.
[22] S. Pettie and V. Ramachandran, An optimal minimum spanning tree algorithm, J. ACM,
49 (2002), pp. 16–34.
[23] V. V. Vazirani, Approximation Algorithms, Springer-Verlag, Berlin, 2001.
[24] A. C.-C. Yao, On constructing minimum spanning trees in k-dimensional spaces and related
problems, SIAM J. Comput., 11 (1982), pp. 721–736.