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 (1985)<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>. | This section is not it the textbook. It is from Tarjan and Vishkin (1985)<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] [https://www.researchgate.net/publication/220617428_An_Efficient_Parallel_Biconnectivity_Algorithm Mirror]</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>. | 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>. | ||
| Line 700: | Line 700: | ||
;Algorithm | ;Algorithm | ||
Assume we are given a connected graph <math>G</math>. | 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. | |||
* | # For every vertex <math>v</math>, calculate the hi and low preorder numbers in the subtree <math>T(v)</math> | ||
# Create the auxiliary graph <math>G'' = (V'', E'')</math> as follows: | |||
#* All edges of <math>G</math> are vertices in <math>G''</math> | |||
#* For each edge <math>(v, w)</math> in <math>G - T</math>, add edge <math> ((p(v),v),(p(w),w))</math> to <math>G''</math> iff <math>v</math> and <math>w</math> are unrelated in <math>T</math> | |||
#* For each edge <math>(v = p(w), w)</math> in <math>T</math>, add edge <math>((p(v), v), (v, w))</math> to <math>G''</math> iff <math>low(w) < v</math> or <math>high(w) \geq v + size(v)</math> | |||
# Compute the connected components of <math>G''</math> | |||
# Assign edges based on their connected components. | |||
;Complexity | ;Complexity | ||