111 citations · 131 across the 17 of their papers we have counts for
5 papers · 1 filter
Simple Length-Constrained Minimum Spanning Trees
D Ellis Hershkowitz, Richard Z Huang
In the length-constrained minimum spanning tree (MST) problem, we are given an -node edge-weighted graph and a length constraint . Our goal is to find a spanning t…
Low-Step Multi-Commodity Flow Emulators
Bernhard Haeupler, D Ellis Hershkowitz, Jason Li +2
We introduce the concept of low-step multi-commodity flow emulators for any undirected, capacitated graph. At a high level, these emulators contain approximate multi-commodity flow…
Efficient Centroid-Linkage Clustering
MohammadHossein Bateni, Laxman Dhulipala, Willem Fletcher +4
We give an efficient algorithm for Centroid-Linkage Hierarchical Agglomerative Clustering (HAC), which computes a -approximate clustering in roughly time. We ob…
New Structures and Algorithms for Length-Constrained Expander Decompositions
Bernhard Haeupler, D Ellis Hershkowitz, Zihan Tan
Expander decompositions form the basis of one of the most flexible paradigms for close-to-linear-time graph algorithms. Length-constrained expander decompositions generalize this p…
It's Hard to HAC with Average Linkage!
MohammadHossein Bateni, Laxman Dhulipala, Kishen N Gowda +3
Average linkage Hierarchical Agglomerative Clustering (HAC) is an extensively studied and applied method for hierarchical clustering. Recent applications to massive datasets have d…