Tuesday, 6 August 2013

Find all the bridges between any to vertex in a directed graph

Find all the bridges between any to vertex in a directed graph

I have an algorithm to find the bridges of a directed graph from a vertex
u to any other vertex which has a O(|V|+|E|) time complexity (based on
DFS). I have to develop an algorithm to find the bridges between any two
vertex u and v in O(|V||E|).
Do you have any suggestions or hints to achieve this?
If I repeat the DFS-Visit for every vertex, only the first time the vertex
are white and the following times the call will do nothing. If I reset the
colour before do that, then the algorithm will be O(|V|^2 + |V||E|).

No comments:

Post a Comment