Approximate Tree Completion and Learning-Augmented Algorithms for Metric Minimum Spanning Trees

Nate Veldt, Thomas Stanley, Benjamin W. Priest +4

Finding a minimum spanning tree (MST) for $n$ points in an arbitrary metric space is a fundamental primitive for hierarchical clustering and many other ML tasks, but this takes $Ω(…