Minimum bottleneck spanning tree vs MST

830 views Asked by At

A MST(minimum spanning tree) is necessarily a MBST(minimum bottleneck spanning tree).

Given a set of points in a 2D plane with the edges of the weight of the Euclidean distance between each pair of point, I want to find the minimum bottleneck edge in the spanning tree (the maximum-weighted edge).

According to my limited knowledge in this field and research on the internet, the best way to calculate this using the MST approach is to do a Delaunay triangulation of the given points, and use the fact that the MST of these points is a subset of the triangulation and then run Kruskal's or Prim's algorithm. Then all I need to do is to find the maximum weight in the MST.

I am wondering if I can do this more efficiently by building a MBST, as I am only looking for the bottleneck edge.

Thanks in advance.

Edit: my current way to find it, both using MST or MBST calculates the weight of all V * (V-1) / 2 edges first, which I consider quite inefficient. I'd like to know if there's an alternative around this.

0

There are 0 answers