Parallel Algorithms: Difference between revisions

Parallel Algorithms (view source)

Revision as of 17:43, 12 May 2020

123 bytes added , 12 May 2020

→‎Biconnectivity

David

Bureaucrats, Interface administrators, Administrators

5,323

edits

@@ Line 691: / Line 691: @@
 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>.
-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>.
+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. There are the equivalence classes of the relation <math>R</math> above.
+Every connected graph consists of biconnected components. These are sets of edges such that every two edges from a set lie on a simple cycle.
+Vertices which connect two biconnected components are called ''articulation points''.
+If these points are removed, the two biconnected components are no longer connected.
 ;Algorithm