Given boruvka's algorithm:
MST T <- empty tree Begin with each vertex v as a component While number of components > 1 For each component c let e = minimum edge out of component c if e is not in T add e to T //merging the two components connected by e
In each phase I'd like to reduce the graph's size, by saying that after each phase - there is actually no need to remember edges that are within each component (because some were inserted to the MST T already and others are not needed). So instead of each component I'd like to put only a single vertex. The only problem comes when I try to construct my edges - an edge between two new vertices (which were two components before) is the one with the smallest weight among all the edges between a vertex in the first component and a vertex in the second. I wanted to implement this in linear time, but I don't see how I can reduce the edges as well, all in linear time?