Finding the Shortest Bottleneck Edge in a Parametric Minimum Spanning Tree

In this note, we focus on a problem studied by Katoh and Tokuyama [8]: Given a parametric graph with edge weights changing linearly in time, find the time value when the weight of the largest MST edge (the so-called bottleneck edge) is minimized. The bottleneck edge weight is of particular interest, because it represents a threshold for connectivity: it is equal to the smallest value r such that the subgraph of edges with weight ^ r stays connected. For this problem, Katoh and Tokuyama [8] have given an O((m8=7n1=7 + mn1=3) polylog n) algorithm, which is faster than the current methods for computing all MSTs over time. Katoh and Tokuyama's method uses advanced data structures for range searching and is therefore difficult to implement. Here, we give a much faster and simpler randomized algorithm that runs in O(n(m=n) " log n + m) expected time for any fixed " ? 0. This time bound is at least as good as O(m log n) and O(n log1+" 0 n + m) for any fixed "0? 0, and almost matches an \Omega (n log n+m) lower bound. The new result is obtained by an interesting combination of techniques from computational geometry and graph data structures. The geometric aspects are similar to those used for the problem of 2-d feasible linear programming with violations from a previous paper [4]