LocalBridge of degree k in Graph

Question

What would be the best algorithm to find localbridge(k) in Graph? A local bridge of degree k is an edge whose removal would enlarge the shortest distance between its two end-points to at least k.

Wikipedia: http://en.wikipedia.org/wiki/Bridge_(interpersonal)#Local_bridge

Answer 1

Run an all-shortest-path-costs algorithm, like the Floyd-Warshall algorithm, but where you use tuples (d1,d2) for distances, instead of the typical real numbers d:

• d1 is the length of the shortest path
• d2 is the length of the second shortest path

This modification to the Floyd-Warshall algorithm should be straightforward.

When you are done running the all-shortest-path-costs algorithm, the localbridge(k) edges are those edges e = {u, v} such that the distance (1,d2) between u and v satisfies d2 >= k.