  We present a deterministic algorithm for computing the sensitivity of a
minimum spanning tree (MST) or shortest path tree in $O(m\log\alpha(m,n))$
time, where $\alpha$ is the inverse-Ackermann function. This improves upon a
long standing bound of $O(m\alpha(m,n))$ established by Tarjan. Our algorithms
are based on an efficient split-findmin data structure, which maintains a
collection of sequences of weighted elements that may be split into smaller
subsequences. As far as we are aware, our split-findmin algorithm is the first
with superlinear but sub-inverse-Ackermann complexity. We also give a reduction
from MST sensitivity to the MST problem itself. Together with the randomized
linear time MST algorithm of Karger, Klein, and Tarjan, this gives another
randomized linear time MST sensitivity algoritm.
