Sublinear Algorithms for Estimating Single-Linkage Clustering Costs

Pan Peng, Christian Sohler, Yi Xu

Single-linkage clustering (SLC) is a fundamental method for hierarchical data analysis. In the distance setting, a $k$-clustering produced by SLC can be obtained by computing a min…