Baba's blog

The "Bridge Tree" of a graph.
By Baba, 10 years ago, In English

http://threads-iiith.quora.com/The-Bridge-Tree-of-a-graph

Any feedback/suggestions are most welcome. :)

  • Vote: I like it
  • +24
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What is the time complexity of the bridge tree building process?

→ Reply
»
6 years ago, # |
← Rev. 4   Vote: I like it +9 Vote: I do not like it

More bridge tree questions:
https://mirror.codeforces.com/contest/1000/problem/E
https://mirror.codeforces.com/contest/652/problem/E

→ Reply
»
4 years ago, # |
  Vote: I like it +6 Vote: I do not like it

I'm so confused. How does it differs from Block-cut tree ? Thanks in advance

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    In a bridge tree, every vertex corresponds to a 2-connected component, and edges correspond to bridges. If edge $$$(a, b)$$$ is on the path $$$u, v$$$ in the bridge tree, then the edge $$$(a, b)$$$ is a bridge that separates $$$u$$$ and $$$v$$$ in the original graph.

    Block-cut trees are kind of similar, with cut vertices instead of bridges. It has the property that if vertex $$$x$$$ is on the path $$$u, v$$$ in the block-cut tree, then it is a cut vertex that separates $$$u$$$ and $$$v$$$ in the original graph.

    → Reply