3

Tarjan's algorithm for finding bridges in a graph is found here: http://en.wikipedia.org/wiki/Bridge_(graph_theory)#Tarjan.27s_Bridge-finding_algorithm.

However, I don't understand the condition for checking if an edge is a bridge. I get that L(w) = w is a necessary condition, but I think that the condition for H(w) < w + ND(w) is redundant, since you're always guaranteed for that to be true (when doing the pre-order traversal, all the vertices in the subtree of w are visited consecutively and are numbered consecutively, and H(W) has to be in the subtree of w, making H(W) < w + ND(W) always true).

So I'm curious if the H(W) < w + ND(W) condition is even necessary, and if so, can you provide an example case where it is needed?

Improve this question

1 Answer 1

Reset to default
1

The L() test, yes, handles loops or cycles. It also handles cross links in unrelated branches in the spanning tree that are to the left (or have lower preorder number).

But here is why I think you need the H() test. The H() test handles cross links to branches in the spanning tree that are unrelated and to the right (or have higher preorder number).

Here is an example. Suppose your graph is:

  A
B   C
|   |
D - E

Where the spanning tree in list form is [A [B [D]] [C [E]]]. But there is also a cross edge from D to E which is rightward with respect to D.

Note that H(D) will be the preorder value for E, the highest number of the spanning tree. Without that edge A-C would be a bridge. It isn't though because of the test on H(D).

Improve this answer
2
  • How do you get a spanning tree of [A [B [D]] [C [E]]] from that graph? Only valid spanning trees that i can see starting in A are: A -> B -> D -> E -> C or A -> C -> E -> D -> B since the graph is a simple single loop Commented Mar 19, 2016 at 23:55
  • @user14780 The example is a cycle. Removing any single edge in a simple cycle gives a spanning tree. So you could also remove undirected edge B-D, or edge C-E as well. Commented Mar 21, 2016 at 6:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.