Author |
Topic: LocalBrdige in Graph (Read 5698 times) |
|
Erik
Newbie
Posts: 27
|
 |
LocalBrdige in Graph
« on: Feb 27th, 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 end-points 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 7th, 2014, 5:58pm » |
Quote Modify
|
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
|
| « Last Edit: Aug 7th, 2014, 11:08pm by towr » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print