wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> LocalBrdige in Graph
        
(Message started by: Erik on Feb 27^th, 2013, 12:11pm)

Title: LocalBrdige in Graph
Post by Erik on Feb 27^th, 2013, 12:11pm

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

Title: Re: LocalBrdige in Graph
Post by israa2010 on Aug 7^th, 2014, 5:58pm

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

// removed spam --towr