Baba's blog

By Baba, 9 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

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

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

»
3 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

  • »
    »
    3 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.