<p>This problem is easier than the problem of sensitivity analysis of minimum spanning trees, which is to determine how much each tree/nontree edge can increase/decrease in weight before the minimum spanning tree changes. The best known algorithm for MST sensitivity analysis appears to be due to <a href="http://arxiv.org/abs/1407.1910" rel="nofollow">Seth Pettie (2005, arXived 2014)</a>, with a running time of O(|E| log alpha(|E|, |V|)). This is very close to optimal (alpha is inverse Ackermann) but also still superlinear. Several randomized algorithms with linear expected running times are known.</p>
Find critical edges of an MST: possible with modified Prim's algorithm?
<p>I came across this question while finding a solution for a "critical edge" problem. The original (C++) problem, which I have already solved, was:</p>

<blockquote>
  <p>Consider a graph G=(V,E). Find how many edges belong to <strong>all</strong> MSTs, how many edges do <strong>not</strong> belong to <strong>any</strong> MST and how many edges belong to some MSTs, but not all.</p>
</blockquote>

<p>Let's call "green", "red" and "yellow", respectively, the edges in the 3 above cases.</p>

<p>After conducting my research, I came across <a href="https://stackoverflow.com/questions/15720155/find-all-critical-edges-of-an-mst">Find all critical edges of an MST</a>, which solves the problem. One would run a modified version of Kruskal's algorithm: if two or more edges of the same weight connect the same components, thus forming a cycle, then all these are yellow edges, i.e., edges that could be included in the MST (or not). Edges that have been indisputably selected are "green" and edges that create a cycle in the same component are "red". So, the original problem has been solved.</p>

<p>The issue with the above algorithm is that it runs in <strong>O( |E| * log|V| )</strong>, which is the running time of Kruskal's algorithm (please correct me if I'm wrong). I was considering whether a modified version of Prim's algortihm could also be used, as it has a better amortized complexity of <strong>O( |E| + |V| log |V| )</strong>, if a Fibonacci heap is used.</p>

<p>My feeling is that a modified version of Prim's algorithm cannot be used here, since we are obliged to iterate all edges based on ascending weight; however, I cannot prove this. So, it is possible to further reduce the complexity of this problem?</p>