5,323
edits
Parallel Algorithms: Difference between revisions
→Biconnectivity
| Line 689: | Line 689: | ||
===Biconnectivity=== | ===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>. | 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: [https://doi.org/10.1137/0214061 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. | 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. | Every connected graph consists of biconnected components. There are the equivalence classes of the relation <math>R</math> above. | ||
;Algorithm | |||
Assume we are given a connected graph <math>G</math>. | |||
* First build a spanning tree <math>T</math>. Record which edges are in the spanning tree. Root the spanning tree. | |||
* Compute the preorder number of all edges using an euler tour | |||
* ... | |||
;Complexity | |||
* <math>O(\log n)</math> time | |||
==Tricks== | ==Tricks== | ||