3
$\begingroup$

I am trying to locate an algorithm that can find ALL vital edges (edges whose deletion strictly increases the cost of the minimum weight spanning tree in the resulting graph) in a minimum weight spanning tree, but have been unable to do so. There appear several algorithms for finding the most vital edges in a minimum weight spanning tree, but not all vital edges in general, and I'm not sure why this is the case.

Any help or assistance would be much appreciated.

Thank you.

1 Answers 1

3

To determine if a given edge $e$ is vital or not, I suppose you can do the following.

Find a minimum spanning tree. If the tree contains the edge $e$, change the weight of $e$ to $\infty$ and find a minimum spanning tree again. If the weight of the minimum spanning tree increases, then $e$ is vital, otherwise it is not.

This is just trying to recast your delete step. Instead of delete, we set its weight to $\infty$ effectively deleting it.

Note: I haven't tried proving it.

  • 0
    An algorithm that is O(the product of the number of edges and the number of vertices) would be nice, but the algorithm that you gave seems to get the job done :)2012-03-27