Find critical edges of MST: perhaps with a modified Prim algorithm?

Question

I came across this issue, finding a solution to the "critical edge" problem. The original (C ++) problem that I already solved was as follows:

Consider the graph G = (V, E). Find how many edges belong to all MSTs, how many edges do not belong to any MST, and how many edges belong to some MSTs, but not all.

Let be called "green", "red" and "yellow" respectively edges in 3 cases.

After conducting my research, I came across Find all critical faces of MST , which solves the problem. One could launch a modified version of the Kruskal 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. Ribs that can be included in the MST (or not), Ribs that have been undeniably selected are “green” and the edges that create a loop in one component are “red”. So, the original problem is solved.

The problem with the above algorithm is that it runs in O (| E | * log | V |) , which is the runtime of the Kruskal algorithm (please correct me if I am wrong). I considered using a modified version of Prim algortihm since it has the best amortized complexity O (| E | + | V | log | V |) if the Fibonacci heap is b.

It seems to me that a modified version of the Prim algorithm cannot be used here, since we are obliged to iterate all the edges according to increasing weight; however, I cannot prove it. So, can you further reduce the complexity of this problem?

Answer 1

, , , , / / . MST, -, Seth Pettie (2005, arXived 2014) O (| E | log alpha (| E |, | V |)). (- Ackermann), . .