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. |
Article policies
|
Find sources: Google ( books · news · scholar · free images · WP refs) · FENS · JSTOR · TWL |
This
level-5 vital article is rated Start-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | |||||||||||
|
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)
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)
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. |
Article policies
|
Find sources: Google ( books · news · scholar · free images · WP refs) · FENS · JSTOR · TWL |
This
level-5 vital article is rated Start-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | |||||||||||
|
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)
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)