Hierarchical Agglomerative Graph Clustering
                    in Nearly-Linear Time

         Laxman Dhulipala 1 David Eisenstat 2 Jakub acki
                                2 Vahab Mirrokni 2 Jessica Shi 1

             Abstract                first proposed nearly 50 years ago (King, 1967; Lance &
    We study the widely used hierarchical agglom-       Williams, 1967; Sneath & Sokal, 1973).
    erative clustering (HAC) algorithm on edge-        A HAC algorithm takes as input a set of n poi ...