Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

up vote 3 down vote accepted

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.

share|improve this answer
    
Or are you looking for a more efficient algorithm? (Because this algorithm just drops out from the definition, I suppose) –  Aryabhata Mar 27 '12 at 5:58
    
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 :) –  Steve Jacobsen Mar 27 '12 at 14:51

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.