Author 
Topic: LocalBrdige in Graph (Read 5698 times) 

Erik
Newbie
Posts: 27


LocalBrdige in Graph
« on: Feb 27^{th}, 2013, 12:11pm » 
Quote Modify

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


IP Logged 



israa2010
Newbie
Gender:
Posts: 1


Re: LocalBrdige in Graph
« Reply #1 on: Aug 7^{th}, 2014, 5:58pm » 
Quote Modify

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

« Last Edit: Aug 7^{th}, 2014, 11:08pm by towr » 
IP Logged 



