Talk:Bridge (graph theory)

This is the talk page for discussing improvements to the Bridge (graph theory) article.
This is not a forum for general discussion of the article's subject.

Put new text under old text. Click here to start a new topic.
New to Wikipedia? Welcome! Learn to edit; get help.

Article policies

Find sources: Google (books · news · scholar · free images · WP refs) · FENS · JSTOR · TWL

slicker algorithm

There is a slicker algorithm for finding bridges that I have been using for many years, but at the moment I can't recall where it comes from. Perform a DFS and number the vertices N(v) in the order of discovery. Now define this function: L(v) is the least N(w) over those w reachable from v by taking zero or more tree edges (i.e. downwards) then exactly one back edge. Then a tree edge (u,v), where u is the parent of v, is a bridge iff L(v)>N(u). L(v) can be computed with an easy recurrence, so the whole lot is linear time and has less baggage than Tarjan's algorithm. Does anyone know where this comes from? McKay (talk) 03:21, 9 August 2011 (UTC)[reply]

This actually is exactly Tarjan's algorithm, except that you're not doing the check of H(v)s.71.236.64.18 (talk) 22:44, 29 October 2012 (UTC)[reply]

If you constructed the spanning tree by performing a DFS with preorder labeling, then it seems calculating and checking H(v)s would be unnecessary. If a vertex u was reachable in the graph from a vertex in the subtree rooted at w, then the edge leading to it would be chosen during DFS, it would become a part of the subtree rooted at w, and its label would always be smaller than (label of w + ND(w)).

But if you follow the presented algorithm exactly and first construct the spanning tree and then label it in a separate pass, you can have edges in the graph from a vertex v to a vertex v' such that v' isn't a descendant of v in the spanning tree and then the H(v) check becomes necessary. Splitting the building of the spanning tree and the labeling of it into separate steps kind of seems like a needlessly complicated way to explain the algorithm.188.146.72.114 (talk) 18:12, 10 August 2016 (UTC)[reply]

188.146.72.114 is quite right. The algorithm I describe is not Tarjan's algorithm. Tarjan's algorithm uses any spanning tree and numbers it in postorder, whereas my algorithm requires a depth-first tree and numbers it in preorder. I'm fairly sure I didn't invent it, but I've been using it since the 1980s. Note that L(v) is the lowpoint function used in the standard algorithm for finding cut vertices, which may be a clue as to where it appears. McKay (talk) 04:01, 1 November 2017 (UTC)[reply]

Isthmus vs. Bridge of subgraph

What is the best way to have both bridge = isthmus and bridge of a subgraph explained? Should it be in two sections of this one article? Should it be in separate articles, one called "Bridge (graph theory) (isthmus)" (for instance) and the other called "Bridge (graph theory) (of a subgraph)" (for instance)? (With these titles the "(graph theory)" could be omitted.) I'm looking for suggestions and whatever rules may apply. Zaslav (talk) 06:12, 17 May 2014 (UTC)[reply]