3
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Raphael Aug 22 '14 at 5:51
  • $\begingroup$ 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. $\endgroup$ – orezvani Aug 22 '14 at 6:05
  • $\begingroup$ 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. $\endgroup$ – Juho Aug 22 '14 at 6:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.