title: How to compute a minimum bottleneck spanning tree in linear time?
body: <p>We can find a minimum bottleneck spanning tree in O(E log*V) in the worst case by using Kruskal's algorithm. This is because every minimum spanning tree is a minimum bottleneck spanning tree. </p>
  
  <p>But I got stuck on this job-interview question from <a href="https://www.coursera.org/course/algs4partII" rel="noreferrer">this</a> course.</p>
  
  <blockquote>
    <p>How can we find a minimum bottleneck spanning tree in linear time even in the worst case. Note that we can assume that we can compute the median of n keys in linear time in the worst case.</p>
  </blockquote>