# Applications of min spanning trees

What are the significant applications of minimum spanning trees?

After doing some research online and in several textbooks, I have found three real-world applications:

• Building a connected network. There are scenarios where we have a limited set of possible routes, and we want to select a subset that will make our network (e.g., electrical grid, computer network) fully connected at the lowest cost.

• Clustering. If you want to cluster a bunch of points into $k$ clusters, then one approach is to compute a minimum spanning tree and then drop the $k-1$ most expensive edges of the MST. This separates the MST into a forest with $k$ connected components; each component is a cluster. (I confess I'm not very clear on whether anyone uses this clustering method in practice, and if so, what domains it is useful in.)

• Traveling salesman problem. There's a straightforward way to use the MST to get a $2$-approximation to the optimal solution to the traveling salesman problem, and the Christofides' heuristic uses MSTs to get a $1.5$-approximation. (One could reasonably question how real-world this is, though, as there are other approximation algorithms for the traveling salesman problem that will typically do even better in practice.)

I have found vague references to other applications, but I have not found details. Are there other significant real-world applications of minimum spanning trees, and if so, how do they work?

• I ran into the same issue when standing in for that lecture. One vague notion I found was that MSTs are used in many more (approximation, heuristic, ...) algorithms as subroutine. – Raphael Aug 22 '14 at 5:51
• You can first look at the properties of a spanning tree, and then guess its applications. For example, its cut property helps in partitioning, or, its spanning+minimality helps in finding lower bound for approximations. – orezvani Aug 22 '14 at 6:05
• A more concrete application of MSTs in approximation algorithms arise with Steiner tree problems. A basic 2-approximation for the minimum cost Steiner tree uses an MST. An even better approximation algorithm using randomized rounding and iterative rounding computes an MST at the first step. – Juho Aug 22 '14 at 6:52