Fast parallel algorithm for the single link heuristics of hierarchical clustering

A fast parallel algorithm of single link heuristics of hierarchical clustering is presented. Its time processor product is optimal and the parallel time is the square of the logarithm. The algorithm is based on computing a minimum spanning tree which can be done in O(log² n) time using O(n²/logⁿ) processors. The main gap to be filled is to compute a hierarchical clustering tree (dendrogram) from a minimum spanning tree. The author proves that this can be done in O(log n) time using O(n ) processors. Therefore, the overall time-processor product of O(n²) is optimal