5,323
edits
Parallel Algorithms: Difference between revisions
→Graph Connectivity
| Line 687: | Line 687: | ||
;Notes | ;Notes | ||
* The progression of edge weights up the tree are monotonically increasing so there are no cycles | * The progression of edge weights up the tree are monotonically increasing so there are no cycles | ||
===Biconnectivity=== | |||
This section is not it the textbook. It is from Tarjan and Vishkin<ref name="tarjan1985biconnectivity">Robert E. Tarjan, and Uzi Vishkin. ''An Efficient Parallel Biconnectivity Algorithm'' (1985). SIAM Journal on Computing. DOI: /10.1137/0214061 [https://epubs.siam.org/doi/10.1137/0214061 https://epubs.siam.org/doi/10.1137/0214061]</ref>. | |||
A graph is biconnected if for every two vertices <math>v_1</math> and <math>v_2</math>, there is a simple cycle containing <math>v_1</math> and <math>v_2</math>. This defines an equivalence relation <math>v_1 R v_2</math>. Intuitively this means that for any two vertices, there are at least two paths from <math>v_1</math> to <math>v_2</math>. If any vertex and its edges are removed from a biconnected graph, it still remains connected. | |||
Every connected graph consists of biconnected components. | |||
==Tricks== | ==Tricks== | ||