<p>First, after each stage throw away any isolated vertices. With these vertices removed (even when the graph is disconnected) the number of vertices in the next stage will be at most twice the number of edges.</p>

<p>Next, use the fact that (with isolated vertices removed, in each stage after the first) $|V|\le 2|E|$ to simplify the time bound in each stage (after the first) from $O(|V|+|E|)$ to $O(|E|)$.</p>

<p>Finally, observe that at each stage $|E|$ goes down by a factor of two, so all these $O(|E|)$ bounds add in a geometric series to be linear in the size of the original graph.</p>

CC BY-SA 3.0
2015-04-06T06:01:12.830Z
2015-04-06T06:01:12.830Z
David Eppstein
<p>I'm having a difficult time understanding Camerini's algorithm because there are very few clear explanations online. The goal is to find a <a href="http://en.wikipedia.org/wiki/Minimum_bottleneck_spanning_tree">minimum-bottleneck spanning tree</a> in linear time. </p>

<p>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.</p>

<p>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|).</p>

<p>What do I misunderstand about this algorithm?</p>

CC BY-SA 3.0
2015-04-06T05:54:03.760Z
`$|V|$ is not guaranteed to decrease in any predictable fashion`: the number of *edges* decreases in the $i$-th recursion to $|E|/(2^i)$.
hengxin
CC BY-SA 3.0
2015-04-06T16:07:46.580Z
Isn't this a home work problem in my course?
Chandra Chekuri
CC BY-SA 3.0
2015-04-06T20:45:29.507Z
@Chandra Indeed. I will include this question as a citation. It is in the homework that "[y]ou may use any source at your disposal - paper, electronic, or human - but you must cite every source that you use." Furthermore, I'm not asking for a complete explanation of the algorithm, but a single specific question I had that required an understanding of the algorithm to ask. StackOverflow and its communities are usually quite good at flagging questions that reduce to "Do my homework for me!" but this question was not tagged as such.
Mark Miller
CC BY-SA 3.0
2015-04-06T20:45:37.137Z
If you think I am overstepping the use of this clause, I can submit an $O((|V|+|E|)Ack^{-1}(|E|))$ draft I created a few days ago without knowing of this algorithm.
Mark Miller
<graph-algorithms><tree>
How does Camerini's algorithm for minimum-bottleneck-spanning-tree run in linear time?
Mark Miller
# How does Camerini's algorithm for minimum-bottleneck-spanning-tree run in linear time?

(Asked by: username_0 on 2015-04-06)

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](http://en.wikipedia.org/wiki/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?

**Tags:** graph-algorithms, tree

> **Comments:**
> **username_1**: `$|V|$ is not guaranteed to decrease in any predictable fashion`: the number of *edges* decreases in the $i$-th recursion to $|E|/(2^i)$.  
> **username_2**: Isn't this a home work problem in my course?  
> **username_0**: @Chandra Indeed. I will include this question as a citation. It is in the homework that "[y]ou may use any source at your disposal - paper, electronic, or human - but you must cite every source that you use." Furthermore, I'm not asking for a complete explanation of the algorithm, but a single specific question I had that required an understanding of the algorithm to ask. StackOverflow and its communities are usually quite good at flagging questions that reduce to "Do my homework for me!" but this question was not tagged as such.  
> **username_0**: If you think I am overstepping the use of this clause, I can submit an $O((|V|+|E|)Ack^{-1}(|E|))$ draft I created a few days ago without knowing of this algorithm.  

---

## 1 answers

### Answer by username_3 on 2015-04-06. Score: 5 | Accepted answer

First, after each stage throw away any isolated vertices. With these vertices removed (even when the graph is disconnected) the number of vertices in the next stage will be at most twice the number of edges.

Next, use the fact that (with isolated vertices removed, in each stage after the first) $|V|\le 2|E|$ to simplify the time bound in each stage (after the first) from $O(|V|+|E|)$ to $O(|E|)$.

Finally, observe that at each stage $|E|$ goes down by a factor of two, so all these $O(|E|)$ bounds add in a geometric series to be linear in the size of the original graph.


---

