I'm having a difficult time understanding Camerini's algorithm because there are very few clear explanations online. The goal is to find a minimum-bottleneck spanning tree in linear time.
Camerini's algorithm does this by splitting the edges by weight into heavy and light halves in O(|E|) time, then building a maximal forest from the light edges. If there is only one tree, then it recurses on the lighter half of edges, but if there are multiple trees, it reduces each tree to a super-vertex, then recurses with the new set of vertices and the heavy edges.
I don't understand how this can run in linear time. If the forest-finding runs in O(|V|+|E|) time, and |V| is not guaranteed to decrease in any predictable fashion, then the algorithm should be bounded by O(|V| log |V| + |E|).
What do I misunderstand about this algorithm?