

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 endpoints 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 allshortestpathcosts algorithm, like the FloydWarshall 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 FloydWarshall algorithm should be straightforward. When you are done running the allshortestpathcosts 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 

Powered by YaBB 1 Gold  SP 1.4! Forum software copyright © 20002004 Yet another Bulletin Board 